DEV Community

dev.to staff
dev.to staff

Posted on

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!

Top comments (21)

Collapse
 
spaciecat profile image
Spacie • Edited

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
Collapse
 
spaciecat profile image
Spacie • Edited

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}
Collapse
 
dawagnbr profile image
dawagnbr • Edited

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 
Collapse
 
coreyja profile image
Corey Alexander • Edited

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\""
        );
    }
}
Collapse
 
arieberesteanu profile image
Arie Beresteanu

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

Collapse
 
auroratide profile image
Timothy Foster

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

factor(factorial(n))
Collapse
 
auroratide profile image
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)
Collapse
 
choroba profile image
E. Choroba • Edited

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.

Collapse
 
alvaromontoro profile image
Alvaro Montoro • Edited

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.

Collapse
 
maskedman99 profile image
Rohit Prasad

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')
Collapse
 
peter279k profile image
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;
      }
    }
  }

  $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;
}
Collapse
 
cloudyhug profile image
cloudyhug

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.

Collapse
 
kesprit profile image
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
    }

    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: " * ")
}
Collapse
 
margo1993 profile image
margo1993

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
}
Collapse
 
oscherler profile image
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 } )
].
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode
Collapse
 
oscherler profile image
Olivier “Ölbaum” Scherler

Too bad @stevemoon didn’t do this one, I would have liked to compare. :-)

Collapse
 
johncip profile image
jmc • Edited

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 " * ")))

Collapse
 
jasman7799 profile image
Jarod Smith • Edited
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;
}