C++で素数判定機を作る

自然数があってそれが素数であるかどうかを高速に判定できたらこの上ない喜びを感じることができますよね。この記事では、C++で素数判定機を作成し、より高速に動作するように改良を重ねていきたいと思います。

注意事項

添付しているソースコードはC++17のGCCコンパイラで動作確認をしています。
また今回のソースコードは、ユーザーが標準入力からオーバーフローしないような自然数を入力してくれるという前提で書いています。（例外処理とか書いても本質とは関係のないところでソースコードが複雑になるだけなので）

試し割り

まずはもっとも基本的なアルゴリズムである試し割りを実装します。

アルゴリズム

与えられた自然数$N$に対して$2$以上$N$未満の自然数で割っていって、割り切れるかどうかを確認していきます。計算量は$O(N)$です。

is_prime_v1.cpp

#include <iostream>

// 素数ならばtrue、合成数ならばfalseを返す関数
bool isPrime(const int n){
    if(n == 1) return false;
    for(int i = 2; i < n; ++i){
        if(n % i == 0) return false;
    }
    return true;
}

int main(){
  	int n;
  	std::cin >> n; 
   
  	if(isPrime(n)) std::cout << n << "は素数です" << std::endl;
  	else std::cout << n << "は素数ではありません" << std::endl;
}

改良版試し割り①

ただ小さい数から割っていくだけでも、工夫によって高速化することができます。例えば、$2$以上$N$未満の数で割り切れるかを試していましたが、これを$2$以上$\sqrt{N}$以下の自然数で割り切れるかを確認すればOKです。なぜならば、すべての合成数$N$は$2$以上$\sqrt{N}$以下の自然数で割り切れるからです。

すべての合成数Nが2以上√N以下の自然数で割り切れることの証明

以下では背理法によってこの命題を示します。急いでいる方は飛ばしても大丈夫です。(といっても爆速で証明できるのですが)

$2$以上の最小の約数$X$が$X>\sqrt{N}$を満たすと仮定する。
$X$は$N$の約数なので$XY=N$となるような自然数$Y$が存在する。
これは$Y<\sqrt{N}$より、$Y<X$となり、$X$が$2$以上の最小の約数であることに矛盾する。
よって命題は示された。

アルゴリズム

与えられた自然数$N$に対して$2$以上$\sqrt{N}$以下の自然数で割っていって、割り切れるかどうかを確認していきます。計算量は$O(\sqrt{N})$です。

is_prime_v2.cpp

#include <iostream>

// 素数ならばtrue、合成数ならばfalseを返す関数
bool isPrime(const int n){
    if(n == 1) return false;
    for(long long i = 2; i * i <= n; ++i){
        if(n % i == 0) return false;
    }
    return true;
}

int main(){
  	int n;
  	std::cin >> n; 
   
  	if(isPrime(n)) std::cout << n << "は素数です" << std::endl;
  	else std::cout << n << "は素数ではありません" << std::endl;
}

改良版試し割り➁

実は試し割りはまだ高速化できます。改良版試し割り➁では$2$以上$\sqrt{N}$以下の全ての自然数で割れるかどうかを試していましたが、素数で割り切れるかどうかを確かめればいいはずです。素数を列挙する方法としてエラトステネスの篩という手法がありますが、今回は別の方法で素数の候補を見つけてみようと思います。

以下の命題を使います。
「$2$と$3$を除くすべての素数は非負整数$k$を用いて$6k\pm1$とあらわされる。」

おまけ程度の証明

急いでいる人は読み飛ばしても大丈夫です。

自然数は非負整数$k$を用いて以下の6つに分類される。

1. $6k$
2. $6k+1$
3. $6k+2=2(3k+1)$
4. $6k+3=3(2k+1)$
5. $6k+4=2(3k+2)$
6. $6k+5$
   $6k$、$6k+2$、$6k+3$、$6k+4$はそれぞれ$6$、$2$、$3$、$2$で割り切れるため素数ではない。したがって$2$と$3$を除くすべての素数は$6k\pm1$の形式であらわされる。

アルゴリズム

与えられた自然数$N$に対して$2$や$3$、また$5$以上$\sqrt{N}$以下の$6k\pm1$型の自然数で割っていって、割り切れるかどうかを確認していきます。計算量は改良版試し割り➀とオーダー程度の違いしかなく、$O(\sqrt{N})$です。

is_prime_v3.cpp

#include <iostream>

// 素数ならばtrue、合成数ならばfalseを返す関数
bool isPrime(const int n){
    if(n == 1) return false;
    if(n == 2 || n == 3) return true;
    if(n % 2 == 0 || n % 3 == 0) return false;
    for(long long i = 5; i * i <= n; i += 6){
        if(n % i == 0 || n % (i + 2) == 0) return false;
    }
    return true;
}

int main(){
  	int n;
  	std::cin >> n; 
   
  	if(isPrime(n)) std::cout << n << "は素数です" << std::endl;
  	else std::cout << n << "は素数ではありません" << std::endl;
}

おわりに

とりあえず、試し割りをいろいろなパターンで実装してみました。今後はより高度な高速化も行っていこうと思います。