Edited at

素数判定 in C/C++

More than 1 year has passed since last update.

エラトステネスの篩は以前に書いたのだが、このアルゴリズムはある1つの数が素数かどうかを判定するには向いていない。

今回は、試し割りによって数nの素数判定を行う関数bool is_prime(const unsigned n)を実装する。


愚直な実装

bool is_prime(const unsigned n){

switch(n){
case 0: // fall-through
case 1: return false;
case 2: return true;
}

// n > 2 が保証された

for(unsigned i=2;i<n;++i){
if(n%i == 0) return false;
}

return true;
}


「愚直な実装」の問題点

・2~n-1まで試し割りしているが、実は2~$\sqrt{n}$で十分

・奇数・偶数問わず試し割りしているが(2以外の)偶数は素数ではないので、実は奇数のみで試し割りすればよい。


修正した実装

bool is_prime(const unsigned n){

switch(n){
case 0: // fall-through
case 1: return false;
case 2: return true;
} // n > 2 が保証された

if(n%2 == 0) return false;

// 上で i=2 相当は調べたので、i=3から奇数のみ調べる
for(unsigned i=3;i*i<=n;i+=2){
if(n%i == 0) return false;
}

return true;
}


より良い実装

3以上の素数は、6で割ったときの余りが1か5になる。

別の言い方をすると、3以上の素数は6の倍数の前後にのみ存在する。

(自然数 $n$ について、 $6n, 6n+1, 6n+2, 6n+3, 6n+4, 6n+5$ のうち素数になりうるのは $6n+1,6n+5$ のみ)

bool is_prime(const unsigned n){

switch(n){
case 0: // fall-through
case 1: return false;
case 2: // fall-through
case 3: return true;
} // n > 3 が保証された

if(n%2 == 0) return false;
if(n%3 == 0) return false;
// 2と3の倍数でないので6の倍数ではないことが保証された

if(n%6 != 1 && n%6 != 5) return false;
// 6の倍数前後の数(素数かもしれない数)であることが保証された

// 6の倍数前後の数を使って試し割りをする
for(unsigned i=5;i*i<=n;i+=6){
if(n%i == 0) return false; // 6n-1
if(n%(i+2) == 0) return false; // 6n+1
}

return true;
}

6は素数である2と3の積なのでこんなことができる。

次の素数である5を更にかけると30になるが、30で割った余りは役に立つようには思えない。

素数となる数の候補が多すぎるのだ。

$(30n+1,30n+7,30n+11,30n+13,30n+17,30n+19,30n+23,30n+29)$