Find the factorial prime factorization

Motivation

If you try to handle a large number of factorials directly on a computer, for example, 32 bits can only express up to 12 factorials, so a small number suddenly requires multiple multiples.

However, for example, $ 12! = 1 \ times2 \ times3 \ times4 \ times5 \ times6 \ times7 \ times8 \ times9 \ times10 \ times11 \ times12 $ is factored into $ = 2 ^ {10} \ times3 ^ 5 \ times5 ^ It can also be expressed as 2 \ times7 ^ 1 \ times11 ^ 1 $.

algorithm

The number of each prime number that appears when the factorial is factored into prime numbers can be easily obtained as follows.

$ 12! = 1 \ times2 \ times3 \ times4 \ times5 \ times6 \ times7 \ times8 \ times9 \ times10 \ times11 \ times12 $ has a multiple of $ 2 $ that appears $ \ lfloor12 / 2 \ rfloor = 6 $ times, $ 2 ^ A multiple of 2 $ appears $ \ lfloor12 / 2 ^ 2 \ rfloor = 3 $ times, and a multiple of $ 2 ^ 3 $ appears $ \ lfloor12 / 2 ^ 3 \ rfloor = 1 $ times. This $ 6 + 3 + 1 $ is the number of $ 2 $ when $ 12! $ Is factored into prime factors.

The same is true for $ 3 $, which is $ \ lfloor12 / 3 \ rfloor + \ lfloor12 / 3 ^ 2 \ rfloor = 5 $.

Postscript 2014/8/28 It seems that a generalization of this is sometimes called "Legendre's theorem".

Factorial(Wikipedia)

Adrien-Marie Legendre found that the multiplicity of the prime p occurring in the prime factorization of n! can be expressed exactly as $\sum_{i=1}^{\infty} \left \lfloor \frac{n}{p^i} \right \rfloor$

End of postscript

From these, it seems that it will be required by the following procedure. To find the prime factorization of $ n! $, You first need a list of prime numbers up to $ n $, so make this with an Eratosthenes sieve. Then, if you find the quotient of those prime numbers in the first power, the quotient of the squares, and so on, the sum of them is the required number of prime numbers.

Since we prepared an array of $ n $ elements for sieving, there will be restrictions due to memory capacity, but it seems to be advantageous because it is possible to describe in a language that can perform lazy evaluation without wasting memory. I will.

code

factfact.c

#include <stdio.h>

void
factfact(int n) {
  int prime[n+1];
  int i, j;

  for (i = 2; i <= n; i++) {
    prime[i] = 1;
  }
  for (i = 2; i <= n; i++) {
    if (prime[i]) {
      for (j = i*2; j <= n; j += i) {
        prime[j] = 0;
      }
    }
  }
  for (i = 2; i <= n; i++) {
    if (prime[i]) {
      prime[i] = 0;
      for (j = i; j <= n; j *= i) {
        prime[i] += n/j;
      }
      printf("%d^%d\n", i, prime[i]);
    }
  }
  printf("\n");
}

int
main(void) {
  factfact(12);
  factfact(1000000);
  return 0;
}