【Java】素数判定③（サンダラムの篩(ふるい)）

　「エラトステネスの篩」とは別の方法で篩(ふるい)をかけていく方法で、「サンダラムの篩」というものもある。内容的には数学の証明のような感じで、素数と合成数の種類から分類するような感じになる。Wikipedia の説明ではわかりづらいので、こちらのサイトなどを見ると良いだろう。具体的でわかりやすく、C言語のソースも載っている。内容的にはこのソースをほぼそのままで、具体的な値を返すように改造しただけのものである。

●素数のリストを作る②（サンダラムの篩(ふるい)）

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

/**<h1>素数のリストを作る（サンダラムの篩）</h1>
 * <p>整数 n > 1 は、素数または合成数で、合成数だけを篩い落せば素数が残される。</p>
 * @param n ： 取得する素数の最大の値 (>=0) [n を含む]
 * @return<b>List<Integer></b> ： 素数のリスト
 */
public static final List<Integer> primeListSundaram(final int n) {
    final List<Integer> list = new ArrayList<Integer>();
    if (n < 2) {        //n が2以上とわかっていれば、ここは不要
        return list;
    }

    final int h = ((n + 1) >>> 1);    //÷2 の代わり
    final boolean[] sieve = new boolean[h];

    int k;
    for (int i = 1; i * i <= n; i++) {
        for (int j = i; (k = i + j + 2 * i * j) < h; j++) {
            sieve[k] = true;    //k = 4,7,10,12,13,16,17,…
        }
    }

    list.add(2);
    for (int i = 1; i < h; i++) {
        if (!sieve[i]) {
            list.add(2 * i + 1);    //素数の数列
        }
    }
    return list;
}


//メインでは...
int n = 100;
List<Integer> primes = primeListSundaram(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

　今回も他のアルゴリズムと比較も兼ねて、n が０と１のときにも対応させてある。素数とは「１とそれ自身でしか割り切れない、２以上の整数」と定義されているので、不要なら０と１ははじめから除外しても良い（２以上を使うこと前提ならば、関数内冒頭の「if (n < 2)～」は削除しても構わない）。

　サンダラムの篩ではエラトステネスの篩のときのように、篩だけ（boolean[] 配列だけ）の例は掲載しなかったが、この篩は「偶数の合成数と奇数の合成数を篩った数列」であって、素数のフラグそのものではないためだ。エラトステネスの篩と同じようにフラグの配列が欲しければ、関数内でもう１つ配列を作り、最後のリストを作っている部分（list.add(2 * i + 1)）を配列に変えれば良い。ただし、２つ配列を作りオーダーがO(n/2)のためか、篩だけならエラトステネスの篩の方が速い（エラトステネスは配列１つでO(√n)）。またリストを作る場合はO(n/2)で良いためか、サンダラムの篩の方が速い（エラトステネスはO(n)）。実装にもよると思うが、使い分けしても良いかも知れない。

　コードは比較のため、前回に合わせた書き方という感じもあるが、他に参考になったサイトなども載せておこう。配列やリスト、言語の特質なんかもあるかも知れないが、色々試してみると「なるほどな～」と思ったりする(笑)。

（参考）
・サンダラムの篩 (MEMORANDUM)
・サンダラムの篩 (Trivial Contents)
・サンダラムの篩 (私的数学塾)

　もう１つ、現代風のアルゴリズム(?)の「アトキンの篩」というものもある。Wikipedia では英語版しかないが、他のサイトで用例があったので次回やってみよう。


（関連記事）
【Java】素数判定②（エラトステネスの篩(ふるい)）
【Java】素数判定④（アトキンの篩(ふるい)）
【Java】素数判定①（試し割り法）