## DEV Community is a community of 906,671 amazing developers

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

# 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 (21) Spacie • Edited on

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
`````` Spacie • Edited on

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
`````` Timothy Foster

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

``````factor(factorial(n))
`````` Timothy Foster

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 Corey Alexander • Edited on

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\""
);
}
}
`````` E. Choroba • Edited on

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. Alvaro Montoro • Edited on

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')
`````` Olivier “Ölbaum” Scherler

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
`````` cloudyhug

``````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. kesprit

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 {
let numberOfDivision = factorial.numberOfDivision(with: \$1)
return \$0.append("\(\$1)\(numberOfDivision == 1 ? "" : "^\(numberOfDivision)")")
}.joined(separator: " * ")
}
`````` margo1993

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
}
`````` peter279k

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;
}
}
}

foreach(\$result as \$key => \$value) {
if (\$key === 1) {
continue;
}
if(\$value === 1) {
\$answer .= \$key . " * ";
continue;
}
\$answer .= \$key . "^" . \$value . " * ";
}

}

function isPrime(\$n) {
\$count = ceil(sqrt(\$n));
for(\$index=2; \$index<=\$count; \$index++) {
if (\$n % \$index === 0) {
return false;
}
}

return true;
}
`````` jmc • Edited on

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
`````` I'm Luis! \^-^/

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

\s