C++ 素数を求める2種類の方法

素数の求め方を調べた。

素数を求める方法

ひとつ目は愚直な割り算の繰り返し。ふたつ目はエラトステネスのふるい。

割り算を繰り返せば、どんな素数でも求められる。しかし、多くの数を素数か判定するのには遅すぎる。 エラトステネスさえ覚えれば、多くの素数問題は攻略できる。しかし、悲しいことに大きな素数を求めることはできない。

そこで、２種類の方法を使い分ける必要がある。

愚直に求めるサンプルプログラム

bool primeNumber(int n){
    if(n < 2) return false;
    else{
        for(int i = 2; i * i <= n; i++){
            if(n % i == 0) return false;
        }
        return true;
    }
}

与えられた値が素数かを判定する。 n - 1までの値で割り続け、割り切れなければ素数である。√nより大きな自然数ではnを割り切ることはできないので、その部分は処理する必要がない。 なので、ループの範囲は　i * i <= n　と書ける。

１つの値が素数かどうかを判定するこのプログラムの計算量は0(√n)である。
もしもn以下のすべての素数を求めるのであれば、計算量はO(n√n)である。

制約が 1 <= n <= 10^6 だった場合、n以下の素数を全て求めようとするとO(10^6 * 10^3)。TLEする。

エラトステネスのふるい

const int N /*値*/;
void eratosthenes(bool prime[N]){
    rep(i,N) prime[i] = 1;
    prime[0] = prime[1] = 0;
    rep(i,N){
        if(prime[i]){
            for(int j = i + i; j < N; j+=i){
                prime[j] = 0;
            }
        }
    }
}

引数として渡したbool型配列に、素数の情報を詰め込んでくれる。prime[素数] == true。素数ではないとき、値はfalseである。 n以下の素数をすべて求めてくれる。

よくループカウンタを間違える。

計算量はO(n log log n) になる。

どちらを使うのか

10^6までの素数を求めたい→エラトステネス
制約に10^7、10^8とか書いてある→愚直

エラトステネスでは求められないなら、愚直で。 制約の10^8を見て、「エラトステネスじゃ求められない……。他のアルゴリズムあったっけ？」と考える必要はない。（２回もやってる）