We're a place where coders share, stay up-to-date and grow their careers.

Woo 3 days in a row!

I'm not too good when it comes to maths and I'm sure there are loads of more efficient algorithms for finding prime factors, but I think this works!

require 'prime' def decomp n return "1" if n == 1 counts = Hash.new 0 (n / 2).ceil.downto(1).each do |x| next if !Prime.prime? x until n % x > 0 or n == 0 n /= x counts[x] += 1 end end counts.to_a.reverse.map(&proc {|pair| pair[1] > 1 ? "#{pair[0]}^#{pair[1]}" : pair[0]}).join " * " end def test n fact = Math.gamma(n + 1).to_i puts "n = #{n}; n! = #{fact}; decomp(n!) = #{decomp(fact)}" end (1..10).each {|x| test x}

Output:

n = 1; n! = 1; decomp(n!) = 1 n = 2; n! = 2; decomp(n!) = 2 n = 3; n! = 6; decomp(n!) = 2 * 3 n = 4; n! = 24; decomp(n!) = 2^3 * 3 n = 5; n! = 120; decomp(n!) = 2^3 * 3 * 5 n = 6; n! = 720; decomp(n!) = 2^4 * 3^2 * 5 n = 7; n! = 5040; decomp(n!) = 2^4 * 3^2 * 5 * 7 n = 8; n! = 40320; decomp(n!) = 2^7 * 3^2 * 5 * 7 n = 9; n! = 362880; decomp(n!) = 2^7 * 3^4 * 5 * 7 n = 10; n! = 3628800; decomp(n!) = 2^8 * 3^4 * 5^2 * 7

Turns out there's actually a built in method for this ... So just the formatting I guess...

require 'prime' def decomp n fact = Math.gamma(n + 1).to_i "n = #{n}; n! = #{fact}; decomp(n!) = #{n == 1 ? "1" : Prime.prime_division(fact).map(&proc {|pair| pair[1] > 1 ? "#{pair[0]}^#{pair[1]}" : pair[0]}).join(" * ")}" end (1..10).each {|x| puts decomp x}

Woo 3 days in a row!

I'm not too good when it comes to maths and I'm sure there are loads of more efficient algorithms for finding prime factors, but I think this works!

Output:

Turns out there's actually a built in method for this ... So just the formatting I guess...