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

はじめに

普段の開発では教科書的なアルゴリズムに触れる機会がないので、頭の体操を兼ねて「エラトステネスの篩」を使って素数を求めるコードを書いてみました。

コード

• Wikipediaに書かれているアルゴリズムをそのままJavaのコードに書き起こしました。
• 一番面倒だったのは、IntStreamをListに変換する部分でした。
• アルゴリズムの本質とは全く関係のない部分で、やたら時間がかかってしまいました...

PrimeNumberFinder.java

static void printPrimeNumbers(int maxNumber) {

	// ステップ1：「2から上限値までの整数」を探索リストに入れる。
	List<Integer> targetNumbers = IntStream.rangeClosed(2, maxNumber).boxed().collect(Collectors.toList());

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

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

	// ステップ3：探索リストの先頭の値が、引数の平方根に達するまでふるい落とし操作を続ける。
	while(targetNumbers.get(0)<=sqrt) {
		// ステップ2：探索リストの先頭の数を素数リストに入れて、その倍数を探索リストから篩い落とす。
		int firstNum = targetNumbers.get(0);
		primeNumbers.add(firstNum);
		targetNumbers.removeIf(num -> (num % firstNum == 0));
	}

	// ステップ4：探索リストに残った値を素数リストに移して処理終了。
	primeNumbers.addAll(targetNumbers);

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

// printPrimeNumbersの引数に100を指定した時の出力結果
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	

余談

• 中尾ミエさんが「エラトステネスの篩」という曲を歌っているそうですが、歌詞を見ると上記のWikipediaのページの説明とほぼ同じでビックリしました。
• 違う点は「探索リストの先頭の値が、引数の平方根に達するまでふるい落とし操作を続ける」という制約がないこと。
• どうやらNHKのEテレで使われていた曲のようですが、子供向けなのにしっかりした内容でビックリしました。