【Java】素数判定②（エラトステネスの篩(ふるい)）

　前回の isPrime() は１つの数値が素数かどうかを調べる方法だったが、今回の「エラトステネスの篩(ふるい)」は素数かどうかの一覧のような感じのもの。Wikipedia にも書いてあるように、コンピュータがある以前からあるアルゴリズムである。「ユークリッドの互除法」に並んで最古のアルゴリズムとも言われているらしい。故にわかりやすく、色々応用しやすい長所がある。その内容はググればいくらでも出てくるので他のサイトに譲るが、Wikipedia の右端にあるアニメーションを見ているだけでもその方法は十分にわかると思う。

　今回は素数かどうかのフラグを列挙した配列と実際の素数の値を列挙したリストを作ってみよう。

●素数かどうかを判定する②(エラトステネスの篩(ふるい))

/**<h1>エラトステネスの篩（素数フラグ）を作る</h1>
 * <p>偶数以外で、3 から √n までに対して順番に倍数をふるい落としていく。</p>
 * @param n ： 調べる素数の最大の値 (>=0) [n を含む]
 * @return<b>boolean[]</b> ： 素数である数のインデクスが true となる配列
 */
public static final boolean[] eratosthenesSieve(final int n) {
    final boolean[] sieve = new boolean[n + 1];    //素数フラグ
    if (n < 2) {        //n が2以上とわかっていれば、ここは不要
        return sieve;
    }

    sieve[2] = true;

    for (int i = 3; i <= n; i += 2) {    //2の倍数以外(奇数)を候補にする
        sieve[i] = true;
    }

    for (int i = 3; i * i <= n; i += 2) {    //奇数のみ [O(√n[/2])で可]
        if (sieve[i]) {
            for (int j = i * 2; j <= n; j += i) {    //倍数を候補から除外する
                sieve[j] = false;
            }
        }
    }
    return sieve;
}


//メインでは...
int n = 10;
boolean[] sieve = eratosthenesSieve(n);
for (int i = 0; i < sieve.length; i++) {
    System.out.print(sieve[i] + " ");    //素数である i が true になる
}

false false true true false true false true false false false

　真偽値は素数となるインデクスの数が true となる（上の例の場合、[2], [3], [5], [7] が true となっているので、2～10(n) までの数の中で 2, 3, 5, 7 が素数ということを表している）。

　素数とは「１とそれ自身でしか割り切れない、２以上の整数」と定義されているので、０と１ははじめから除外しても良いが、前回の isPrime() が０と１にも対応していたので、比較のため合わせておいた。２以上を使うこと前提ならば、関数内冒頭の「if (n < 2)～」は削除しても構わない。

　コード自体は isPrime() とあまり変わらないので、必要なら前回の解説を見て欲しい。

　もう１つ、今度は具体的な素数の値のリストを返す関数を作ろう。作り方は簡単で、上記のエラトステネスの篩をしながら、true となっている値をリストに追加してくだけだ。

●素数のリストを作る①（エラトステネスの篩(ふるい)）

import java.util.ArrayList;
import java.util.List;

/**<h1>素数のリストを作る（エラトステネスの篩）</h1>
 * <p>偶数以外で、3 から √n までに対して順番に倍数をふるい落としていく。</p>
 * @param n ： 取得する素数の最大の値 (>=0) [n を含む]
 * @return<b>List<Integer></b> ： 素数のリスト
 */
public static final List<Integer> primeListEratosthenes(final int n) {
    final List<Integer> list = new ArrayList<Integer>();
    if (n < 2) {        //n が2以上とわかっていれば、ここは不要
        return list;
    }

    final boolean[] sieve = new boolean[n + 1];    //素数フラグ
    sieve[2] = true;
    list.add(2);

    for (int i = 3; i <= n; i += 2) {    //2の倍数以外(奇数)を候補にする
        sieve[i] = true;
    }

    //エラトステネスのふるい
    for (int i = 3; i <= n; i += 2) {    //奇数のみ[リスト作成のため O(n[/2])]
        if (sieve[i]) {
            list.add(i);
            for (int j = i * 2; j <= n; j += i) {    //倍数を候補から除外する
                sieve[j] = false;
            }
        }
    }

    return list;
}


//メインでは...
int n = 100;
List<Integer> primes = primeListEratosthenes(n);
for (int v : primes) {
    System.out.print(v + " ");
}

2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97

　今回は簡単にするため、List を用いているが、配列を戻値にしても良いだろう。ただ、配列の場合はあらかじめ要素数を決めないといけないので、篩（sieve[i]）が true になっているものをカウントしておいて（上記の例の場合、リストに追加（list.add()）している場所）、カウント後に配列のインスタンスを生成する必要がある。または取り得る最大の個数（上限値）が決まっているなら、引数に配列の参照を受け取り、値を順に追加した上で、最後に追加したインデクスを戻値として返す方法もある（メインではその戻値で [0]～[idx] の間だけ使うようにする）。具体的な値のリストが必要ないなら、篩の真偽値だけの方がもちろん速い。

　ちなみに「n までの素数の個数」は「素数定理」や「ベルトランの仮説」にある通り、「n が十分大きいときには n と 2n の間の素数の個数は n / log n に近いことが言え、特にベルトランの仮説によって保証されている1つの素数の存在よりもより強く、より多くの素数が n と 2n の間に存在していることが分かる」(Wikipedia)と言われているので、「n / log n」で近似してみるのも良いかも知れない。または「ルジャンドルの素数定理」で「n 以下の素数の個数は n/(log n - 1.08366) で近似できる」とか「リーマンゼータ関数」など色々あるようなので、覗いてみると面白いかも知れない。ただ、私もいくつか試してみたが、元々「与えられた数より小さい素数の個数」なので、配列の要素数定義には使えなかった（n + 1 したり、関数の答えを +1 してみたが、素数の個数が必要な配列の要素数を上回る個数になることもある[ArrayIndexOutOfBoundsException]）。いい加減な個数で良いのなら「n * 1.25505871293248 / log n」あたりにしておくと、n までの素数の個数が上回ることはないようだ（この係数は全探索で算出したものなので、Java 以外で適用できるかわからないが…（→実数計算は言語によって微妙に誤差が出るため））。まぁ、無駄は多くなるが n 個で要素数を作っても良いと思う。参考までに素数の個数に関する資料を載せておこう。

（参考）
・素数定理の歴史
・素数個数関数の近似、素数定理、グラフ
・平方数間の素数の個数(1)、平方数間の素数の個数(2)

　ネットに落ちているサンプルコードも同じアルゴリズムでありながら、実装によって実行速度は随分違うので、配列やリスト、真偽値のみなど、用途に合わせて使い分けた方が良いだろう。特にエラトステネスの篩は他のアルゴリズムと違って改造しやすい利点があるので、例えば「開始～終了インデクスの間だけ値を取り出す」とか、n を上限数ではなく「n 個の素数を取り出す」など簡単に作れる。オンラインジャッジでの出題でも利用頻度は高いので、いくつかのパターンをライブラリとして作っておくとかなり役に立つだろう。

　他にも同じ篩系のアルゴリズムとして「サンダラムの篩」というものもある。せっかくなので、比較のためにも少しだけやってみよう。


（関連記事）
【Java】素数判定③（サンダラムの篩(ふるい)）
【Java】素数判定④（アトキンの篩(ふるい)）
【Java】素数判定①（試し割り法）

■参考になる書籍