## Factoring Factorials

### January 24, 2014

Today’s exercise sounds, from the title, like another exercise involving prime numbers and integer factorization, and it is, but it’s really a puzzle from the realm of recreational mathematics: Given a positive integer *n*, compute the prime factorization, including multiplicities, of *n*! = 1 · 2 · … · *n*. You should be able to handle very large *n*, which means that you should *not* compute the factorial before computing the factors, as the intermediate result will be extremely large.

Your task is to write the function described above. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

#include

#include

// reducing numbers from biggest to 2

// 16 -> 2*8 … 8 -> 2*4 … 4 -> 2*2 …

void main(int argc, char **argv) {

int n = atoi(argv[1]);

int *p = (int *) malloc(sizeof(int) * (n + 1));

int i, j, d;

for(i = 0; i 1; i–)

if(p[i]) {

for(j = i + i, d = 2; j <= n; j += i, d++) {

if(p[j]) {

p[i] += p[j];

p[d] += p[j];

p[j] = 0;

}

}

}

printf("1");

for(i = 2; i <= n; i++)

if(p[i])

printf(" * %i^%i", i, p[i]);

printf("\n");

}

Recursivelly adding factorizations

import Data.List

import Data.Monoid

import Data.Numbers.Primes

facfac 1 = Factors [(1, 1)]

facfac n = factorization n `mappend` facfac (n – 1)

— Factorizations Monoid

data Factorization a = Factors [(a, a)] deriving Show

factorization = Factors . map (\ps -> (head ps, length ps)) . group . primeFactors

instance Integral a => Monoid (Factorization a) where

mempty = Factors []

mappend (Factors []) fs = fs

mappend fs (Factors []) = fs

mappend xfs@(Factors (xf@(x, a):xs)) yfs@(Factors (yf@(y, b):ys)) =

case x `compare` y of

EQ -> Factors ((x, a + b):ms)

LT -> Factors (xf:ns)

GT -> Factors (yf:os)

where Factors ms = mappend (Factors xs) (Factors ys)

Factors ns = mappend (Factors xs) yfs

Factors os = mappend xfs (Factors ys)

(Excuse me, I can’t modify previous post)

In C version, we can reduce main loop from “i = n” to “i = n >> 1”.

That version has O(n log log n) and are not needed primes calculation nor mul nor div operations (space is O(n)).

Did in Go using my Project Euler library. Since it’s designed to solve PE problems everything is done with type uint64.

That’s a fun little problem. Here is my solution. It is quick and dirty, not efficient.

Assuming `primes` is already implemented, returning a stream of prime numbers in order, in Haskell,

Another Python version. The optimization suggested by Will Ness did not work (in Python).