素因数分解 Factorize

001 void factorize( int x, vector<int> &factors ){
002     int d, q;
003     while ( x >= 4 && x % 2 == 0 ) {
004         factors.push_back(2);
005         x /= 2;
006     }
007     d = 3; q = x / d;
008     while ( q >= d ){
009         if ( x % d == 0 ) {
010             factors.push_back(d);
011             x = q;
012         } else {
013             d += 2;
014         }
015         q = x / d;
016     }
017     factors.push_back(x);
018 }

エラトステネスの篩（ふるい） The sieve of Eratosthenes

素数の項目で紹介した素数判定プログラムは、与えられた１つの数 x が素数であるか否かを判定するだけでしたが、多くの問題を解く場合、あらかじめ作成された素数表を用いるのが効率的です。

与えられた範囲内の全ての素数を列挙するための高速なアルゴリズムが、エラトステネスの篩（ふるい） The sieve of Eratosthenes です。エラトステネスの篩は、以下の手順で素数表を生成します。ここで、素数表を prime[x] が真ならば x は素数、偽ならば x は合成数（素数ではない整数）であるようなブール型の１次元配列とします。

	2 以上の整数を列挙しておく
	最小である 2 を残して、その倍数をすべて消す
	残った最小の 3 を残して、その倍数をすべて消す
	残った最小の 5 を残して、その倍数をすべて消す
	以下同様に、まだ消えていない最小の数を残してその倍数を消すことを繰り返せば、素数だけが残る

エラトステネスの篩を実装したプログラム例を以下に示します。

001 void eratos ( int n, bool prime[]){
002     for ( int i = 0; i <= n; i++ ) prime[i] = false;
003     // 奇数を素数の候補とする
004     for ( int i = 3; i <= n; i += 2 ) prime[i] = true;
005     prime[2] = true;
006     int limit = (int)sqrt((double)n) + 1;
007     // 合成数でない奇数だけを残す
008     for ( int i = 3; i <= limit; i += 2 ){
009         if ( !prime[i] ) continue;
010         // i は素数　i の倍数をすべて消す
011         for ( int j = i + i; j <= n; j += i ) prime[j] = false;
012     }
013 }

このプログラムは、以下のように多少改良することができます。

void eratos ( int n, bool prime[]){
    for ( int i = 0; i <= n; i++ ) prime[i] = false;
    // 奇数を素数の候補とする
    for ( int i = 3; i <= n; i += 2 ) prime[i] = true;
    prime[2] = true;
    int limit = (int)sqrt((double)n) + 1;
    // 合成数でない奇数だけを残す
    for ( int i = 3; i <= limit; i += 2 ){
        if ( !prime[i] ) continue;
        for ( int j = i * i, k = i * 2; j <= n; j += k )
        prime[j] = false;
    }
}

素数

約数が「1 とその数自身だけ」であるような自然数を素数と言います。素数を小さい順に列挙すると、

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, , ,

となります。1 は素数ではありません。素数は数論において重要な数ですが、コンピュータにおいても、暗号化のアルゴリズムに応用されるなど、重要な役割を果たします。

まずは、与えられた数が素数であるか否かを判定する素数判定のアルゴリズムを考えてみましょう。

誰もが思いつく素朴なアルゴリズムの１つを実装したプログラムを以下に示します。

001 bool isPrime( int x ){
002     if ( x <= 1 ) return false;
003     // 2 から x - 1 までの数で x を割ってみて
004     // 割り切れたら素数ではないので false を返す
005     for ( int i = 2; i < x - 1; i++ ){
006         if ( x % i == 0 ) return false;
007     }
008     return true;
009 }

この素朴な素数判定のアルゴリズムは、以下の２つのポイントに着目することで高速化が図れます。

	2 以外の偶数は素数ではないこと
	2 から x - 1 までではなく、2 から x の平方根までについて割り切れるかどうかをチェックすれば十分である

1 つめのポイントは明らかですが、2 つめのポイントは直感的に分かりにくいかもしれません。例を考えてみましょう。与えられた x が 31 とします。31 の平方根は 5.56... なので、31 が素数であるかどうかは、31 を 2 から 6 までの数で割ってみれば十分ということになります。ではなぜ 6 までで十分なのでしょうか。それは 7 から 30 までの数でもし 31 を割り切れる数が存在するならば、すでにチェックした 2 から 6 までの数に 31 を割り切れる数が必ず存在するからです。この改良を施したアルゴリズムを実装したプログラムを以下に示します。

001 bool isPrime( int x ){
002     if ( x < 2 ) return false;
003     else if ( x == 2 ) return true;
004     if ( x % 2 == 0 ) return false; // 偶数は素数ではない
005     // 3 から開始して 2 づつ増やす→奇数のみチェックする
006     int limit = (int)sqrt((double)x) + 1;
007     for ( int i = 3; i <= limit; i += 2 ){
008         if ( x % i == 0 ) return false;
009     }
010     
011     return true;
012 }

ユークリッドの互除法

ユークリッドの互除法は、

x ≧ y のとき、gcd(x, y) と gcd(y, x%y) は等しい

という定理を用いて、x と y の最大公約数を効率良く求めるアルゴリズムです。
（ここで、x%y は x を y で割った余りを示します）

具体的な例を見てみましょう。

gcd(54, 20)		(54 % 20 = 14)
= gcd(20, 14)		(20 % 14 = 6)
= gcd(14, 6)		(14 % 6 = 2)
= gcd(6, 2)		(6 % 2 = 0)
= gcd(2, 0)
= 2

ユークリッドの互除法を実装したプログラム例です。

001 int gcd( int x, int y ){
002     int r;
003     // x ≧ y を満たすことを保障する
004     if ( x < y ) swap( x, y );
005     
006     while ( y > 0 ){
007         r = x % y;
008         x = y;
009         y = r;
010     }
011     
012     return x;
013 }

定理の証明,,,,

最大公約数

２つの正の整数 x と y の最大公約数とは

x / d と y / d の余りがともに 0 となる d のうち最大のもの

を言います。最大公約数は英語で Greatest Common Divisor と言われ、一般的に gcd と略されます。いくつか例を見てみましょう。

gcd(35, 14) = 7

(公約数 1, 7 のうち最大の数である 7)

gcd(128, 192) = 64

(公約数 1, 2, 4, 8, 16, 32, 64 のうち最大の数である 64)

誰もが思いつく最大公約数を求める方法が、以下の力任せのアルゴリズムです。

001 int gcd( int x, int y ){
002     int n;
003     n = min( x, y ); // x と y の小さい方
004     // n から 1 までの数で、x と y を順に割っていき、
005     // 余りが 0 になったらその数を返す
006     for ( int d = n; d >= 1; d-- ){
007         if ( x % d == 0 && y % d == 0 ) return d;
008     }
009     assert ( false ); // 入力に 0 がきたらエラー
010 }

このアルゴリズムは実用的ではありません。