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