【Java】エラトステネスの篩で素数を求める（その2）

はじめに

前回の投稿のコードは、@swordone さんからの指摘で「リストを全探査して割り算して篩い落とす」という高コストなコードだと判明しました。
そこで、@swordone さんから頂いたヒントを基にして、コードを大幅に直してみました。

コード

前回のコードとの違いは以下の通りです。

• 探索リストをList<Integer>からboolean[]に変更。
  • 「2から上限値までのリスト」の代わりに、「2から上限値までの添え字のリスト」としました。
  • 最初に配列の全要素を素数扱い（true）としておき、篩い落とす時に素数以外の値（false）としました。
• 「リストを全探査して割り算して篩い落とす」のではなく、「篩い落とす値の要素にランダムアクセスして篩い落とす」形に変更。
  • for文のインクリメントを「1ずつ増加」ではなく、「現在の素数（firstNum）の値ずつ増加」させることで、現在の素数（firstNum）の倍数だけを篩い落としています。

PrimeNumberFinder.java

static void printPrimeNumbers2(int maxNumber) {

    // ステップ1：「2から上限値までの整数」を探索リストに入れる。
    boolean[] targetNumbers = new boolean[maxNumber + 1];
    Arrays.fill(targetNumbers, true);
    targetNumbers[0] = false;
    targetNumbers[1] = false;

    // 素数リスト
    List<Integer> primeNumbers = new ArrayList<Integer>();

    int sqrt = (int) Math.sqrt(maxNumber);

    // ステップ3：探索リストの先頭の値が、引数の平方根に達するまでふるい落とし操作を続ける。
    for(int i=2; i<=sqrt; i++) {
        // ステップ2：探索リストの先頭の数を素数とし、その倍数を探索リストから篩い落とす。
        // ※この時、既に篩い落とされた数（false）は除外する。
        int firstNum = i;
        if (targetNumbers[i]) {
            for (int j=i*firstNum; j<targetNumbers.length; j+=firstNum) {
                targetNumbers[j] = false;
            }
        }
    }

    // ステップ4：探索リストに残った値を素数リストに移して処理終了。
    for (int i=2; i<targetNumbers.length; i++) {
        if (targetNumbers[i]) {
            primeNumbers.add(i);
        }
    }

    // 素数の表示
    System.out.println(primeNumbers.stream().map(pNum -> pNum.toString()).collect(Collectors.joining("\t")));
}

どれだけ高速化したか？

• 前回のコードと比べて、10倍以上高速化していました。
• ギレン総帥じゃなくても「圧倒的じゃないか、我が軍は。」と言いたくなるほどの差です。

	上限値が$10^2$	上限値が$10^3$	上限値が$10^4$	上限値が$10^5$
前回のコード	54ms	55ms	61ms	102ms
今回のコード	0ms	1ms	1ms	9ms

まとめ

• 今回のコードを通じて、「計算量」を考慮した開発が重要だと再認識させられました。
  • 今回のコードでも、まだまだ改善できるポイントはあると思いますが...
• @swordone さん、色々とヒントを頂き有難うございました。