loading...

Daily Challenge #7 - Factorial Decomposition

thepracticaldev profile image dev.to staff ・1 min read

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!

Posted on by:

thepracticaldev profile

dev.to staff

@thepracticaldev

The hardworking team behind dev.to ❤️

Discussion

markdown guide
 

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}
 

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
    }

    var primeNumbers: [Int] {
        (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"

var primeNumbers = []int{2,3,5,7,11,13,17,19,23}

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 {
            primeFactors = append(primeFactors, primeNumbers[i])
            number = number / primeNumbers[i]
        } 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: [12],
        out: '2^10 * 3^5 * 5^2 * 7 * 11'
    },
    {
        in: [22],
        out: '2^19 * 3^9 * 5^4 * 7^3 * 11^2 * 13 * 17 * 19'
    },
    {
        in: [25],
        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?