素数

約数が「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 }