ウィルソンの定理を使ってn未満の素数をすべて効率的に生成する方法

本記事では、nより小さいすべての素数を効率的に生成する方法を紹介します。このアプローチではウィルソンの定理（Wilson's theorem）を活用します。ウィルソンの定理によれば、ある数kが素数であるとき、((k - 1)! + 1) mod k の計算結果は必ず0になります。つまり、この性質を利用することで、素数判定を行うことができるのです。

ただし、この手法には注意点があります。CやC++のような言語でそのまま実装すると、階乗の計算によって非常に大きな数が生じるため、標準の整数型では大きな整数を扱えず、正しく動作しません。実際に使用する場合は、多倍長整数（ビッグナンバー）ライブラリの導入や、オーバーフロー対策が必要になります。

アルゴリズム

genAllPrime(n)

Begin
    fact := 1
    for i in range 2 to n-1, do
        fact := fact * (i - 1)
        if (fact + 1) mod i is 0, then
            print i
        end if
    done
End

C++での実装例

以下は、上記のアルゴリズムをC++で実装した例です。ここでは説明のためint型を使用していますが、前述の通り大きなnに対してはオーバーフローが発生する点に留意してください。

#include <iostream>
using namespace std;
void genAllPrimes(int n){
    int fact = 1;
    for(int i=2;i<n;i++){
        fact = fact * (i - 1);
        if ((fact + 1) % i == 0){
            cout<< i << " ";
        }
    }
}
int main() {
    int n = 10;
    genAllPrimes(n);
}

出力結果

2 3 5 7

n = 10 を指定した場合、10未満の素数である「2、3、5、7」が出力されます。

まとめ

ウィルソンの定理を用いた素数生成は、数学的に非常にエレガントなアプローチです。しかし、階乗の計算コストが大きく、数値も急激に膨らむため、実用面ではエラトステネスの篩（ふるい）などの手法の方が一般的に高速かつ効率的とされています。理論的な興味深さと実用性の両面から、両者の違いを理解しておくと良いでしょう。