【Java】エラトステネスの篩

問題

• 整数n以下のすべての素数を見つけよ。

問題の解き方

素数の倍数は合成数（素数ではない数）だから、最初の素数である2から始めてnまでの素数の倍数を合成数とし、合成数以外を素数とします。というざっくりとした説明ですが、これをエラトステネスの篩と言います。

コードを記述する上での考え方

1. サイズn + 1のboolean型の配列isPrimeを用意します。（primeは素数という意味です。）
   ここでは、true=素数で、false=合成数です。
2. 配列を一旦全てtrueで初期化します。
3. 0と1は素数ではないので、isPrime[0]とisPrime[1]はfalseにします。
4. 2からnまでループするfor文を用意して、
5. falseならcontinueによりループを1つ進めます。
   if文の条件式の!isPrime[i]は、isPrime[i] == falseと同義です。
6. trueなら、n以下までのiの倍数をfalseにします。
7. そのすべてのループが終わったら、戻り値として配列isPrimeを返します。

コード例

import java.util.*;

public class Main {
    static boolean[] eratosthenes(int n) {
        boolean[] isPrime = new boolean[n + 1];
        
        Arrays.fill(isPrime, true);
        isPrime[0] = isPrime[1] = false;
        
        for (int i = 2; i <= n; i++) {
            if (!isPrime[i]) {
                continue;
            }
            for (int j = i + i; j <= n; j += i) {
                isPrime[j] = false;
            }
        }
        return isPrime;
    }

    public static void main(String[] args) {
        int n = 30;
        boolean[] isPrime = eratosthenes(n);
        for(int i = 1; i <= n; i++){
            if(isPrime[i]){
                System.out.println(i + "は素数");
            }else{
                System.out.println(i + "は素数ではない");
            }
        }
    }
}