5
5

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 5 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 さん、色々とヒントを頂き有難うございました。
5
5
3

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
  3. You can use dark theme
What you can do with signing up
5
5

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?