Help us understand the problem. What is going on with this article?

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

More than 5 years have passed since last update.

動機

大きな数の階乗を直接計算機上で扱おうとすると、例えば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;
}
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした