Today's challenge will require a bit of mathematical prowess. Those who were fans of the Project Euler challenges might have some fun with this one from user g964 from CodeWars:
The aim of this [challenge] is to decompose
n!
(factorial n) into its prime factors. Prime numbers should be in increasing order. When the exponent of a prime number is 1, don't print the exponent.Examples:
n = 22; decomp(22) -> "2^19 * 3^9 * 5^4 * 7^3 * 11^2 * 13 * 17 * 19"
n = 25; decomp(25) -> "2^22 * 3^10 * 5^6 * 7^3 * 11^2 * 13 * 17 * 19 * 23"Explanation:
n = 12; decomp(12) -> "2^10 * 3^5 * 5^2 * 7 * 11"
12! is divisible by 2 ten times, by 3 five times, by 5 two times and by 7 and 11 only once.
Thank you to CodeWars, who has licensed redistribution of this challenge under the 2-Clause BSD License!
Want to propose a challenge for a future post? Email yo+challenge@dev.to with your suggestions!
Top comments (21)
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...
C++
Output:
Here is my Rust version! These are getting long including the tests, so I might have to find a better way to post em here! Maybe I'll start posting embeds to their Github repo 🤔 (But I don't know if I can embed a single file from a repo...)
Anyways here is today's!
I took a optimization, by never actually calculating the full factorial. Instead I do the prime decomposition, on each of the factorial values (2..n) and append those lists of prime numbers together. This list will be the same as a prime decomposition of the full factorial.
From here I count the occurrences of each of the prime numbers and the format a string matching the examples!
Here is a FORTRAN 90 answer (the module and an example program):
The result looks like:
12! = 479001600 = 2^ 6 + 3^ 4 + 5^ 2 + 7^ 1 + 11^ 1
Note: I hard coded n=12 but I could made n be read from the command line
I can use any language right? How about MATLAB ;)
But here's a haskell solution just for fun:
Perl solution, not using any math libraries:
For 22, it prints 2¹⁹ * 3⁹ * 5⁴ * 7³ * 11² * 13 * 17 * 19.
JavaScript
Not perfect, but it seems to work now. The previous answer I deleted only calculated for the number itself, and not the factorial.
And here is a demo on CodePen.
Python
Here is my simple solution to finish this problem with PHP:
Haskell
The
decomp
function creates a(factor, power)
map describing the decomposition of an integer. ThedecompFactorial
function creates this decomposition for all integers from2
ton
, then merges the maps summing the values for each key. The result is then pretty printed.