# Daily Challenge #7 - Factorial Decomposition

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!

### Discussion 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 ? "#{pair}^#{pair}" : pair}).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 ? "#{pair}^#{pair}" : pair}).join(" * ")}"
end
(1..10).each {|x| puts decomp x}


C++

struct factor {
long prime;
long power;
};

auto decompose_factorial(long n) {
std::vector<factor> result;
for (long i = 2; i <= n; ++i) {
auto prime = true;
for (auto &f : result) {
for (auto r = i; r % f.prime == 0; r /= f.prime) {
prime = false;
++f.power;
}
}
if (prime) {
result.push_back({i, 1});
}
}
return result;
}

int main() {
long n = 25;
auto decomposition = decompose_factorial(n);
std::cout << "n = " << n << std::endl;
std::cout << "decomp(n!) = ";
for (auto &f : decomposition) {
std::cout << f.prime;
if (f.power > 1) {
std::cout << "^" << f.power;
}
std::cout << " ";
}
std::cout << std::endl;
return EXIT_SUCCESS;
}



Output:

n = 25
decomp(n!) = 2^22 3^10 5^6 7^3 11^2 13 17 19 23


I can use any language right? How about MATLAB ;)

factor(factorial(n))


But here's a haskell solution just for fun:

import Data.List

prime_factors :: Int -> [Int]
prime_factors 1 = []
prime_factors n = next_factor : (prime_factors $div n next_factor) where next_factor = head [i | i <- [2..n], 0 == mod n i] decomp :: Int -> [Int] decomp = sort . decomp' where decomp' 1 = [] decomp' n = prime_factors n ++ decomp' (n - 1)  Here is a FORTRAN 90 answer (the module and an example program): MODULE decompose IMPLICIT NONE CONTAINS SUBROUTINE decomp(n,primes,powers,factorial) INTEGER, INTENT(IN) :: n INTEGER, ALLOCATABLE, INTENT(OUT) :: primes(:),powers(:) INTEGER, INTENT(OUT) :: factorial INTEGER :: i,j,m,current INTEGER, DIMENSION(25) :: lowPrimes DATA lowPrimes /2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97/ IF (n.GT.100) THEN !can't handle a too big number PRINT *, "Choose a number less than 100" RETURN END IF m=COUNT(lowPrimes.LE.n) !how many integers less or equal to n !initial values ALLOCATE(primes(m),powers(m)) primes=lowPrimes(1:m) powers=0 factorial = 1 !decomposing n! number by number DO i=2,n factorial = factorial * i current=i DO j=1,m IF (MOD(current , primes(j)) .EQ. 0) THEN current = INT(current / primes(j)) powers(j) = powers(j) +1 END IF IF (current.EQ.1) EXIT ! we are done decomposing i END DO !j END DO !i END SUBROUTINE decomp END MODULE decompose PROGRAM testDecompose USE decompose IMPLICIT NONE INTEGER :: myInt,m,i INTEGER, ALLOCATABLE :: pr(:),po(:) INTEGER :: fa myInt = 12 CALL decomp(n=myInt,primes=pr,powers=po,factorial=fa) !printing the result: WRITE (*,"(i3,a4,i12,a3)",advance='no') myInt,"! = ",fa," = " m = SIZE(pr) DO i=1,m IF (po(i).GT. 0) WRITE(*,"(i2,a1,i2)" , advance='no') pr(i),"^",po(i) IF (i.LT.m) WRITE(*,"(a3)" , advance='no') " + " END DO PRINT *," " END PROGRAM testDecompose  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 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! use std::collections::HashMap; fn prime_decomposition(n: u32) -> Vec<u32> { let mut output = vec![]; let mut curr = n; for i in 2..(n + 1) { while curr % i == 0 { output.push(i); curr = curr / i; } } output } fn count_occurances(list: Vec<u32>) -> Vec<(u32, u32)> { let mut counts: HashMap<u32, u32> = HashMap::new(); for x in list { let count = counts.entry(x).or_insert(0); *count += 1; } counts .keys() .map(|key| (*key, *counts.get(key).unwrap())) .collect() } pub fn factorial_decomposition(n: u32) -> Vec<(u32, u32)> { if n == 0 || n == 1 { vec![(1, 1)] } else { let mut factors: Vec<u32> = vec![]; for i in 2..(n + 1) { factors.append(&mut prime_decomposition(i)); } let mut output = count_occurances(factors); output.sort(); output } } // "n = 12; decomp(12) -> \"2^10 * 3^5 * 5^2 * 7 * 11\"" pub fn fac_decomp_string(n: u32) -> String { fn format_single_factorial(x: &(u32, u32)) -> String { if x.1 == 1 { format!("{}", x.0) } else { format!("{}^{}", x.0, x.1) } } let factorial_decomposition = factorial_decomposition(n); let fac_string = factorial_decomposition .iter() .map(format_single_factorial) .collect::<Vec<String>>() .join(" * "); format!( "n = {n}; decomp({n}) -> \"{decomp}\"", n = n, decomp = fac_string ) } #[cfg(test)] mod tests { use crate::*; fn sorted_counted_prime_decomp(n: u32) -> Vec<(u32, u32)> { let mut output: Vec<(u32, u32)> = count_occurances(prime_decomposition(n)); output.sort(); output } #[test] fn prime_decomposition_works_for_prime_numbers() { assert_eq!(sorted_counted_prime_decomp(2), vec![(2, 1)]); assert_eq!(sorted_counted_prime_decomp(3), vec![(3, 1)]); assert_eq!(sorted_counted_prime_decomp(5), vec![(5, 1)]); assert_eq!(sorted_counted_prime_decomp(7), vec![(7, 1)]); assert_eq!(sorted_counted_prime_decomp(11), vec![(11, 1)]); } #[test] fn prime_decomposition_works_for_factors_of_2() { assert_eq!(sorted_counted_prime_decomp(2), vec![(2, 1)]); assert_eq!(sorted_counted_prime_decomp(4), vec![(2, 2)]); assert_eq!(sorted_counted_prime_decomp(8), vec![(2, 3)]); assert_eq!(sorted_counted_prime_decomp(16), vec![(2, 4)]); } #[test] fn prime_decomposition_works_for_more_complex_numbers() { assert_eq!(sorted_counted_prime_decomp(10), vec![(2, 1), (5, 1)]); assert_eq!(sorted_counted_prime_decomp(6), vec![(2, 1), (3, 1)]); assert_eq!(sorted_counted_prime_decomp(15), vec![(3, 1), (5, 1)]); } #[test] fn simple_factorial_decomposition() { assert_eq!(factorial_decomposition(2), vec![(2, 1)]); assert_eq!(factorial_decomposition(3), vec![(2, 1), (3, 1)]); assert_eq!(factorial_decomposition(4), vec![(2, 3), (3, 1)]); assert_eq!(factorial_decomposition(5), vec![(2, 3), (3, 1), (5, 1)]); } #[test] fn factorial_decomposition_of_edge_cases() { assert_eq!(factorial_decomposition(1), vec![(1, 1)]); assert_eq!(factorial_decomposition(0), vec![(1, 1)]); } #[test] fn factorial_decomposition_of_examples() { assert_eq!( factorial_decomposition(12), vec![(2, 10), (3, 5), (5, 2), (7, 1), (11, 1)] ); assert_eq!( factorial_decomposition(22), vec![ (2, 19), (3, 9), (5, 4), (7, 3), (11, 2), (13, 1), (17, 1), (19, 1) ] ); assert_eq!( factorial_decomposition(25), vec![ (2, 22), (3, 10), (5, 6), (7, 3), (11, 2), (13, 1), (17, 1), (19, 1), (23, 1), ] ); } #[test] fn formatting_works() { assert_eq!(fac_decomp_string(0), "n = 0; decomp(0) -> \"1\""); assert_eq!(fac_decomp_string(1), "n = 1; decomp(1) -> \"1\""); assert_eq!( fac_decomp_string(12), "n = 12; decomp(12) -> \"2^10 * 3^5 * 5^2 * 7 * 11\"" ); assert_eq!( fac_decomp_string(22), "n = 22; decomp(22) -> \"2^19 * 3^9 * 5^4 * 7^3 * 11^2 * 13 * 17 * 19\"" ); assert_eq!( fac_decomp_string(25), "n = 25; decomp(25) -> \"2^22 * 3^10 * 5^6 * 7^3 * 11^2 * 13 * 17 * 19 * 23\"" ); } }  Perl solution, not using any math libraries: #!/usr/bin/perl use warnings; use strict; use utf8; use feature qw{ say }; use open OUT => ':encoding(UTF-8)', ':std'; sub is_prime { my ($p) = @_;
for my $d (2 .. sqrt$p) {
return if 0 == $p %$d;
}
return 1
}

sub factor {
my ($n) = @_; my @f; for my$p (2 .. $n) { next unless is_prime($p);
if (0 == $n %$p) {
push @f, $p;$n = $n /$p;
redo
}
}
return @f
}

{   my %digit;
@digit{0 .. 9} = qw( ⁰ ¹ ² ³ ⁴ ⁵ ⁶ ⁷ ⁸ ⁹ );
sub exponent {
join "", map $digit{$_}, split //, shift
}
}

my %exponent;
my $n = shift; for my$p (2 .. $n) { ++$exponent{$_} for factor($p);
}

say join ' * ',
map $_ . ($exponent{$_} == 1 ? "" : exponent($exponent{$_})), sort {$a <=> $b } keys %exponent;  For 22, it prints 2¹⁹ * 3⁹ * 5⁴ * 7³ * 11² * 13 * 17 * 19. JavaScript const decomp = number => { // function that adds the dividers of a number to a "dividers object" const subdecomp = (number, subdividers) => { let remainder = number // from 2 to square root of the number for (x = 2; x <= Math.sqrt(number); x++) { // check if it can divide the number if (remainder % x === 0) { // add it as a key to a results object if (!subdividers[x]) subdividers[x] = 0; // while it can be a divisor, add +1 to the key and update number while (remainder % x === 0) { subdividers[x]++; remainder = remainder / x; } } } // if after all there's still a remaining number, it is a divisor too if (remainder > 1) { if (!subdividers[remainder]) subdividers[remainder] = 1; else subdividers[remainder] += 1; } return subdividers; } // initial dividers: none! let dividers = {} // calculate the dividers for each number used in the factorial for (let x = 2; x <= number; x++) dividers = subdecomp(x, dividers); // generate a html string with the result return Object.keys(dividers).reduce((acc, curr) => dividers[curr] === 1 ? ${acc} ${curr} : ${acc} ${curr}<sup>${dividers[curr]}</sup>
, decomp(${number}) = ); }  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 import math var = int(input("Enter the number: ")) fac = math.factorial(var) def prime(x): for i in range(3,x-1,2): if x%i == 0: return False return True def decomp(x,fac): for i in range(fac): if fac % x**i != 0: return i-1 print('2^' + str(decomp(2,fac)), end='') for i in range(3,var+1,2): if prime(i) == True: e = decomp(i,fac) if e != 1: print(' * ' + str(i) + '^' + str(e), end='') else: print(' * ' + str(i), end='') else: continue print('\n')  I’m learning Erlang. I’m not really happy with my solution yet, I feel it could be simpler. I’d rather keep functions that do one thing, though, and avoid decompose_factorial_into_factors_and_group(X, Y, Z, []) or something. Hence I didn’t save on the single-argument versions, or combine unrelated functions. -module( decomp ). -export( [ is_prime/1, decomp/1, fact_decomp/1, print/1 ] ). -include_lib("eunit/include/eunit.hrl"). is_prime( 1 ) -> false; is_prime( N ) when N > 0 -> is_prime( N, 2, floor( math:sqrt( N ) ) ). is_prime( _N, Start, End ) when Start > End -> true; is_prime( N, Start, _End ) when N rem Start == 0 -> false; is_prime( N, Start, End ) -> is_prime( N, Start + 1, End ). decomp( N ) when N > 1 -> lists:reverse( decomp( N, 2, [] ) ). decomp( N, Start, Factors ) when Start > N -> Factors; decomp( N, Start, Factors ) -> case is_prime( Start ) and ( N rem Start == 0 ) of true -> decomp( N div Start, 2, [ Start | Factors ] ); false -> decomp( N, Start + 1, Factors ) end. group_factors( Factors ) -> group_factors( Factors, #{} ). group_factors( [], Map ) -> Map; group_factors( [ Head | Rest ], Map ) -> Current = maps:get( Head, Map, 0 ), Updated = maps:put( Head, Current + 1, Map ), group_factors( Rest, Updated ). fact_decomp( N ) -> group_factors( lists:flatmap( fun decomp/1, lists:seq( 2, N ) ) ). format_factor( { Fact, Exp } ) -> case Exp of 1 -> io_lib:format( "~p", [ Fact ] ); _ -> io_lib:format( "~p^~p", [ Fact, Exp ] ) end. format_factors( Facts ) -> string:join( lists:map( fun format_factor/1, lists:sort( maps:to_list( Facts ) ) ), " * " ). print( N ) -> io:fwrite( "~s~n", [ format_factors( fact_decomp( N ) ) ] ). % TESTS prime_list_test() -> Primes = [ 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997 ], lists:foreach( fun( N ) -> ?assert( is_prime( N ) =:= lists:member( N, Primes ) ) end, lists:seq( 1, 1000 ) ). decomp_test() -> [ ?assert( decomp( 2 ) =:= [ 2 ] ), ?assert( decomp( 3 ) =:= [ 3 ] ), ?assert( decomp( 4 ) =:= [ 2, 2 ] ), ?assert( decomp( 5 ) =:= [ 5 ] ), ?assert( decomp( 6 ) =:= [ 2, 3 ] ), ?assert( decomp( 7 ) =:= [ 7 ] ), ?assert( decomp( 8 ) =:= [ 2, 2, 2 ] ), ?assert( decomp( 9 ) =:= [ 3, 3 ] ), ?assert( decomp( 10 ) =:= [ 2, 5 ] ), ?assert( decomp( 11 ) =:= [ 11 ] ), ?assert( decomp( 12 ) =:= [ 2, 2, 3 ] ), ?assert( decomp( 13 ) =:= [ 13 ] ), ?assert( decomp( 14 ) =:= [ 2, 7 ] ), ?assert( decomp( 15 ) =:= [ 3, 5 ] ), ?assert( decomp( 16 ) =:= [ 2, 2, 2, 2 ] ), ?assert( decomp( 17 ) =:= [ 17 ] ), ?assert( decomp( 18 ) =:= [ 2, 3, 3 ] ), ?assert( decomp( 19 ) =:= [ 19 ] ), ?assert( decomp( 20 ) =:= [ 2, 2, 5 ] ) ]. fact_decomp_test() -> [ ?assert( fact_decomp( 2 ) =:= #{ 2 => 1 } ), ?assert( fact_decomp( 6 ) =:= #{ 2 => 4, 3 => 2, 5 => 1 } ), ?assert( fact_decomp( 13 ) =:= #{ 2 => 10, 3 => 5, 5 => 2, 7 => 1, 11 => 1, 13 => 1 } ), ?assert( fact_decomp( 22 ) =:= #{ 2 => 19, 3 => 9, 5 => 4, 7 => 3, 11 => 2, 13 => 1, 17 => 1, 19 => 1 } ), ?assert( fact_decomp( 25 ) =:= #{ 2 => 22, 3 => 10, 5 => 6, 7 => 3, 11 => 2, 13 => 1, 17 => 1, 19 => 1, 23 => 1 } ), ?assert( fact_decomp( 12 ) =:= #{ 2 => 10, 3 => 5, 5 => 2, 7 => 1, 11 => 1 } ) ].  Try with: % erl 1> c(decomp). {ok,decomp} 2> decomp:test(). All 3 tests passed. ok 3> decomp:print(22). 2^19 * 3^9 * 5^4 * 7^3 * 11^2 * 13 * 17 * 19 ok  Too bad @stevemoon didn’t do this one, I would have liked to compare. :-) Haskell import Data.List import qualified Data.Map.Strict as Map primes :: [Int] primes = filterPrime [2..] where filterPrime (p : xs) = p : filterPrime [x | x <- xs, x mod p /= 0] decomp :: Int -> Map.Map Int Int decomp n = if n == 1 || n elem lowerPrimes then Map.singleton n 1 else Map.filter (/= 0)$ divide Nothing 0 n lowerPrimes Map.empty
where
lowerPrimes = takeWhile (<= n) primes
divide Nothing             _     1 _             factors = factors
divide (Just current)      count 1 _             factors = Map.insert current count factors
divide Nothing             _     n (p : ps)      factors = divide (Just p) 0 n ps factors
divide curr@(Just current) count n prim@(p : ps) factors =
case n divMod current of
(q, 0) -> divide curr (count + 1) q prim factors
_      -> divide (Just p) 0 n ps (Map.insert current count factors)

decompFactorial :: Int -> String
decompFactorial n = toString $foldl1 (Map.unionWith (+))$ map decomp [2..n]
where toString = intercalate " + " . Map.foldlWithKey (\acc k v -> (show k ++ "^" ++ show v) : acc) []


The decomp function creates a (factor, power) map describing the decomposition of an integer. The decompFactorial function creates this decomposition for all integers from 2 to n, then merges the maps summing the values for each key. The result is then pretty printed.

My solution in Swift, factorial numbers are too big for Int but it's really bored to deal with NSDecimalNumber :

extension Int {
var factorial: UInt64 {
(1...self).reduce(into: UInt64(1)) { $0 *= UInt64($1) }
}

func numberOfDivision(with number: Int) -> Int {
guard number != 1 else { return 1 }
var loop = 0
var value = self.factorial
while value % UInt64(number) == 0 {
value /= UInt64(number)
loop += 1
}
return loop
}

(1..<self).filter { number in
number > 1 && !(2..<number).contains { number % $0 == 0 } } } } func decomp(factorial: Int) -> String { factorial.primeNumbers.reduce(into: [String]()) { let numberOfDivision = factorial.numberOfDivision(with:$1)
return $0.append("\($1)\(numberOfDivision == 1 ? "" : "^\(numberOfDivision)")")
}.joined(separator: " * ")
}


I hardcoded prime numbers but here it is

package utils

import "fmt"

func DecomposeFactorial(number int) string {
var totalPrimeFactos []int
for number > 1 {
primeFactors := findPrimaryNumbers(number)
totalPrimeFactos = append(totalPrimeFactos, primeFactors...)
number--
}

decomposedFactorial := ""
for i, pn := range primeNumbers {
count := elemCount(totalPrimeFactos, pn)

if i  != 0 && count > 0 {
decomposedFactorial += " * "
}

if count > 1 {
decomposedFactorial += fmt.Sprintf("%d^%d", pn, count)
} else if count > 0 {
decomposedFactorial += fmt.Sprintf("%d", pn)
}
}

return decomposedFactorial
}

func findPrimaryNumbers(number int) []int {
var primeFactors []int

i := 0

for number > 1 {
if number % primeNumbers[i] == 0 {
} else {
i++
}
}

return primeFactors
}

func elemCount(array []int, item int) int {
count := 0
for _, l := range array {
if l == item {
count++
}
}
return count
}


Here is my simple solution to finish this problem with PHP:

function decomp($n) {$result = [];
$index = 2; for($index=2; $index <=$n; $index++) {$number = $index;$numberIndex = 2;
if (isPrime($number) === false) { while (isPrime($number) === false) {
if ($number %$numberIndex === 0) {
if (array_key_exists((string)$numberIndex,$result) === true) {
$result[(string)$numberIndex] += 1;
} else {
$result[(string)$numberIndex] = 1;
}

$number = (int)($number / $numberIndex); } else {$numberIndex += 1;
}
}

if (array_key_exists((string)$number,$result)) {
$result[(string)$number] += 1;
} else {
$result[(string)$number] = 1;
}
}

if (isPrime($index) === true) { if (array_key_exists((string)$index, $result)) {$result[(string)$index] += 1; } else {$result[(string)$index] = 1; } } }$answer = "";
foreach($result as$key => $value) { if ($key === 1) {
continue;
}
if($value === 1) {$answer .= $key . " * "; continue; }$answer .= $key . "^" .$value . " * ";
}

return substr($answer, 0, -3); } function isPrime($n) {
$count = ceil(sqrt($n));
for($index=2;$index<=$count;$index++) {
if ($n %$index === 0) {
return false;
}
}

return true;
}


Clojure:

(defn factors [n]
(loop [res [], f 2, n n]
(cond
(= n 1)           res
(zero? (rem n f)) (recur (conj res f) f (quot n f))
:else             (recur res (inc f) n))))

(defn format-entry [[k v]]
(apply str (if (= v 1) [k] [k \^ v])))

(defn decomp [n]
(->> (range 2 (inc n))
(mapcat factors)
(reduce #(merge-with + %1 {%2 1}) (sorted-map))
(map format-entry)
(clojure.string/join " * ")))



function decompose(n) {
if (typeof(n) !== 'number')
throw new Error('must be an integer');
const factorial = getFactorial(n);
const factors = factorize(factorial);
const factorFrequencyArray = parseFactors(factors);
const formattedStr = stringify(factorFrequencyArray);
return formattedStr;
}
function stringify(exponents) {
let str = '';
let i = 0;
exponents.forEach(exponent => {
if (exponents[i] === 1)
str += ${i} * ; else if (exponents[i] !== 0) str += ${i}^${exponents[i]} * ; i++; }); return str.substring(0, str.length - 3); } // O(n) function getFactorial(n) { let factorial = 1n; for(let i = 1n; i <= n; i ++) factorial *= i; return factorial; } // O(n) function parseFactors(factors) { let exponents = Array(57).fill(0); factors.forEach(factor => exponents[factor]++); return exponents; } // O(log(n)) function factorize(n) { const primes = [2n,3n,5n,7n,11n,13n,17n,19n,23n,29n, 31n,37n,43n,47n,53n,59n,61n,67n,71n,73n,79n,83n,89n,97n]; let primeIndex = 0; let factors = []; while(!primes.includes(n)) { if (n % primes[primeIndex] === 0n) { factors.push(primes[primeIndex]); n = n / primes[primeIndex]; primeIndex = 0; } else primeIndex++; } factors.push(n); return factors; }  Solution const revexp = (x, y) => x % y ? 0 : 1 + revexp(x/y, y); const decomp = n => { let seive = Array(n+1).fill(1); for (let i=2; i<=n; i++) { if (seive[i]) for(let j=2*i; j<=n; j+=i) { seive[j] = 0; seive[i] += revexp(j, i); } } return seive .slice(2) .map((exp, ind) => exp > 1 ? ${ind+2}^${exp} : exp ? ${ind+2} : '')
.filter(x => !!x)
.join(' * ');
}


Test

const test = require('./tester');
const decomp = require('./challenge-7');
test (decomp, [
{
in: ,
out: '2^10 * 3^5 * 5^2 * 7 * 11'
},
{
in: ,
out: '2^19 * 3^9 * 5^4 * 7^3 * 11^2 * 13 * 17 * 19'
},
{
in: ,
out:'2^22 * 3^10 * 5^6 * 7^3 * 11^2 * 13 * 17 * 19 * 23'
}
]);


Result

[PASSED]  Case #1: 2^10 * 3^5 * 5^2 * 7 * 11
[PASSED]  Case #2: 2^19 * 3^9 * 5^4 * 7^3 * 11^2 * 13 * 17 * 19
[PASSED]  Case #3: 2^22 * 3^10 * 5^6 * 7^3 * 11^2 * 13 * 17 * 19 * 23


None of these examples work with Google's public key...
taking too long.
Any way to speed up?

\s

How are you developing it? Maybe we can take a look?  