LoginSignup
2

More than 3 years have passed since last update.

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

Last updated at Posted at 2019-03-14

はじめに

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

コード

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

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
2