C++における素数判定アルゴリズムの解説【試し割り法とフェルマー法】

この記事では、与えられた数値Nが素数であるかどうかを判定する方法について解説します。

素数判定（Primality Test）とは、与えられた数が素数かどうかを調べるために用いられるアルゴリズムのことです。

素数とは、1とその数自身でしか割り切れない数のことです。例：2、3、5、7。

問題の例

入力：11
出力：Yes（素数である）

基本的な素数判定方法（試し割り法）

素数判定には複数の手法があります。

最もシンプルな方法は、Nより小さいすべての数で割り切れるかを確認することです。1つでもNを割り切る数が存在すれば、Nは素数ではありません。

具体的には、i = 2 から n-1 までのすべての値について確認します。n % i == 0 となるiが存在すれば、nは素数ではありません。

アルゴリズムを高速化する2つのポイント

この方法は、以下の改良を加えることで大幅に効率化できます。

1. √nまで調べれば十分
nの約数は必ず「√n以下の値」と「√n以上の値」のペアで構成されるため、√nまで確認すればすべての約数候補をカバーできます。これにより、ループ回数を大幅に削減できます。

2. 2と3を先に判定し、6k±1の形で調べる
2と3による割り算を事前にチェックしておけば、それ以降の素数候補はすべて「6k±1」の形（5、7、11、13、17、19…）で表されます。そのため、ループ変数を5から始めて6ずつ増加させ、i と i+2 の2つだけを確認すればよいことになります。

試し割り法の実装例

サンプルコード

#include <iostream>
using namespace std;
bool isPrimeNumber(int n){
    if (n <= 1)
        return false;
    if (n <= 3)
        return true;
    if (n % 2 == 0 || n % 3 == 0)
        return false;
    for (int i = 5; i * i <= n; i = i + 6)
        if (n % i == 0 || n % (i + 2) == 0)
            return false;
    return true;
}
int main() {
    int n = 341;
    if (isPrimeNumber(n))
        cout << n << " は素数です。";
    else
        cout << n << " は素数ではありません。";
    return 0;
}

出力

341 は素数ではありません。

341 = 11 × 31 と分解できるため、素数ではないと正しく判定されています。

フェルマーの小定理を利用した素数判定

より高速に素数判定を行う方法として、フェルマーの小定理に基づくフェルマー法があります。

フェルマーの小定理：Nが素数であるとき、1 ≤ a ≤ n-1 を満たすすべての整数aに対して、以下の関係が成り立ちます。

an-1 ≡ 1 (mod n)
または
an-1 % n = 1

この定理を利用すると、ランダムに選んだ値aがこの性質を満たすかを確認することで、確率的に素数判定を行えます。判定の精度は試行回数kを増やすことで向上します。

なお、フェルマー法は確率的アルゴリズムであるため、カーマイケル数のような特殊な合成数に対しては誤って「素数」と判定する可能性がある点に注意が必要です。

フェルマー法の実装例

サンプルコード

#include <iostream>
#include <math.h>
using namespace std;
int power(int a, unsigned int n, int p) {
    int res = 1;
    a = a % p;
    while (n > 0){
        if (n & 1)
            res = (res*a) % p;
        n = n/2;
        a = (a*a) % p;
    }
    return res;
}
int gcd(int a, int b) {
    if(a < b)
        return gcd(b, a);
    else if(a%b == 0)
        return b;
    else return gcd(b, a%b);
}
bool isPrime(unsigned int n, int k) {
    if (n <= 1 || n == 4) return false;
    if (n <= 3) return true;
    while (k>0){
        int a = 2 + rand()%(n-4);
        if (gcd(n, a) != 1)
            return false;
        if (power(a, n-1, n) != 1)
            return false;
        k--;
    }
    return true;
}
int main() {
    int k = 3, n = 23;
    if(isPrime(n, k)){
        cout << n << " は素数です";
    }
    else
        cout << n << " は素数ではありません";
    return 0;
}

出力

23 は素数です

まとめ

素数判定には、確実に判定できる試し割り法と、高速なフェルマー法があります。小さな数や確実性が求められるケースでは√nまで判定する試し割り法が適しており、非常に大きな数を高速に処理したいケースではフェルマー法のような確率的アルゴリズムが有効です。用途に応じて使い分けましょう。