階乗の素因数分解を求める

動機

大きな数の階乗を直接計算機上で扱おうとすると、例えば32bitなら12の階乗までしか表現できないので、ちょっとした数字でいきなり多倍長演算が必要になってきます。

しかし、例えば $12!=1\times2\times3\times4\times5\times6\times7\times8\times9\times10\times11\times12$ は、素因数分解して $=2^{10}\times3^5\times5^2\times7^1\times11^1$ とも表現できます。

アルゴリズム

階乗を素因数分解したときに各素数が何個出現するかは、次のように容易に求められます。

$12!=1\times2\times3\times4\times5\times6\times7\times8\times9\times10\times11\times12$ には $2$ の倍数が $\lfloor12/2\rfloor=6$ 回出現し、 $2^2$ の倍数が $\lfloor12/2^2\rfloor=3$ 回出現し、 $2^3$ の倍数が $\lfloor12/2^3\rfloor=1$ 回出現します。この $6+3+1$ が、 $12!$ を素因数分解したときの $2$ の個数というわけです。

$3$ についても同様で、$\lfloor12/3\rfloor+\lfloor12/3^2\rfloor=5$ となります。

追記 2014/8/28
これを一般化したものを、「ルジャンドルの定理」ということもあるようです。

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$$

追記終わり

これらから次のような手順で求められそうです。 $n!$ の素因数分解を求めるには、まず $n$ までの素数のリストが必要になりますので、これをエラトステネスのふるいで作っておきます。そして、それらの素数の1乗での商、2乗での商、……を順に求めれば、それらの和が、素数の必要個数となるわけです。

ふるいのために $n$ 要素の配列を用意したので、メモリ容量による制約が発生してしまいますが、遅延評価のできる言語であれば無駄にメモリを消費しない記述ができるので、有利と思われます。

コード

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