基礎おさらい素数編その2
n以下の素数を列挙する手法について。
2以上n以下の整数を全て挙げ、そこから2で割り切れるものをのぞき、残ったうちから3で割り切れるものをのぞき、残ったうちから … mで割り切れるものをのぞく、というのを繰り返していくことで列挙できる。
private static int MAX_N = 10000;
private static boolean[] isPrime = new boolean[MAX_N + 1]; // iが素数かどうか
public static List<Integer> sieve(int n) {
List<Integer> res = new ArrayList<Integer>();
Arrays.fill(isPrime, true);
isPrime[0] = isPrime[1] = false;
for (int i = 2; i * i <= n; i++) {
if (isPrime[i]) {
res.add(i);
for (int j = 2 * i; j <= n; j += i) {
// iをのぞくiの倍数を全てのぞく
isPrime[j] = false;
}
}
}
Collections.sort(res);
return res;
}