【Java】素数判定③（アトキンの篩(ふるい)）

　「より現代的なアルゴリズム」(Wikipedia)と書いてあるので、たぶんそうなのだろう(笑)。残念ながら英語版しかないのだが、「エラトステネスの篩」のような篩系のアルゴリズムで、「アトキンの篩」というものもある。内容的には更なる奇数の分類わけという感じだが、説明は大変そうなので、こちらのサイトへ丸投げしよう(笑)。私も「ふむふむナルホド」と頷きつつ、たぶん本当の意味は理解していない(笑)。「奇数を分類し、いくつかの方程式の解が奇数個なら素数」という話が書いてあるね。とりあえず色々試してみたら確かに正しい答えが出たので、私としては問題ない(笑)。

（参考）
・アトキンのふるい

　内容的にはいくつかのソースを試して、一番高速だったものを、具体的な値を返すように改造しただけのものだ。コードもほぼそのまま。

●素数のリストを作る②（アトキンの篩(ふるい)）

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

/**<h1>素数のリストを作る（アトキンの篩）</h1>
 * <p>奇数を分類わけし、いくつかの方程式の解での判別と平方数を取り除く篩をかける。</p>
 * @param n ： 取得する素数の最大の値 (>=0) [n を含む]
 * @return<b>List<Integer></b> ： 素数のリスト
 */
public static final List<Integer> primeListAtkin(final int n) {
    final List<Integer> list = new ArrayList<Integer>();
    if (n < 2) {        //n が2以上とわかっていれば、ここは不要
        return list;
    }
    list.add(2);
    if (n == 2) {       //n が3以上とわかっていれば、ここは不要
        return list;
    }

    final boolean[] sieve = new boolean[n + 1];
    final int sqr = (int)Math.sqrt(n);

    int k;
    for (int i = 1; i <= 5; i += 4) {
        for (int y = i; y <= sqr; y += 6) {
            for (int x = 1; x <= sqr && (k = 4 * x * x + y * y) <= n; x++) {
                sieve[k] = !sieve[k];
            }
            for (int x = y + 1; x <= sqr && (k = 3 * x * x - y * y) <= n; x += 2) {
                sieve[k] = !sieve[k];
            }
        }
    }
    for (int i = 2; i <= 4; i += 2) {
        for (int y = i; y <= sqr; y += 6) {
            for (int x = 1; x <= sqr && (k = 3 * x * x + y * y) <= n; x += 2) {
                sieve[k] = !sieve[k];
            }
            for (int x = y + 1; x <= sqr && (k = 3 * x * x - y * y) <= n; x += 2) {
                sieve[k] = !sieve[k];
            }
        }
    }
    for (int i = 1; i <= 2; ++i) {
        for (int y = 3; y <= sqr; y += 6) {
            for (int x = i; x <= sqr && (k = 4 * x * x + y * y) <= n; x += 3) {
                sieve[k] = !sieve[k];
            }
        }
    }
    for (int i = 5; i <= sqr; i += 2) {
        if (sieve[i]) {
            for (int j = i * i; j <= n; j += i * i) {
                sieve[j] = false;
            }
        }
    }
    sieve[2] = sieve[3] = true;

    for (int i = 3; i <= n; i += 2) {
        if (sieve[i]) {
            list.add(i);
        }
    }
    return list;
}


//メインでは...
int n = 100;
List<Integer> primes = primeListAtkin(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)～」「if (n == 2)～」は削除しても構わない）。なるべく同じ条件で比較したかったので、「エラトステネスの篩」や「サンダラムの篩」のコードに合わせたら、関数冒頭が少し長くなってしまった。

　実際にこれまでに作った「エラトステネスの篩」と「サンダラムの篩」とこの「アトキンの篩」を比較してみると、「アトキンの篩」「サンダラムの篩」「エラトステネスの篩」の順に速い。ただし、篩(ふるい)の真偽値（sieve[]）でだけなら、「アトキンの篩」「エラトステネスの篩」「サンダラムの篩」となった。実装の仕方もあるのだろうが、やはりコンピュータ時代に生み出された「アトキンの篩」のアルゴリズムの方が比較的速いようだ。とは言え「エラトステネスの篩」は改造しやすいため、出題に合わせて最適化しやすいメリットもある。逆に数式が複雑に絡むコードは改造がしづらく、手を加えればバグを埋め込むことにもなり兼ねないので、スピード特化で使うのも良い気がする。結局は複数のアルゴリズムを知っている方がメリットを活かせるのかも知れない。

　ググっていて感じたのは「サンダラムの篩」はあまり例がないのに対し、「アトキンの篩」は思いのほか実装例がたくさんあったことだ。なので色々試したが、やはりなるべく平方根や除算を使わず、シンプルな実装の方が速かった。isPrime() のとき書いたポイントは非常に小さなことだけど、実は意外と効果は高い。以下にその実装例を挙げておくが、アルゴリズムはすべて同じなわけだから、その「ちょっとした違い」で実行速度が変わることを感じてみるのも勉強になるかも知れない。

（参考）
・アトキンのふるい
・エラトステネスの篩 vs アトキンの篩
・アトキンの篩
・ダメ出し：アトキンの篩
・Rubyで、「エラトステネスのふるい」を改良したと言われる「アトキンのふるい」をいまさら実装する
・Atkinの篩


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