LoginSignup
4

More than 3 years have passed since last update.

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

Last updated at Posted at 2019-03-18

はじめに

前回の投稿のコードは、@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 さん、色々とヒントを頂き有難うございました。

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
What you can do with signing up
4