はじめに

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

コード

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テレで使われていた曲のようですが、子供向けなのにしっかりした内容でビックリしました。

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

はじめに

コード

余談