エラトステネスのふるい

目的

$1$から$N$までの素数を$O(N\log\log{N})$で列挙します。

計算量

$O(N\log\log N)$

使い方

boolean[] isPrime
isPrime[i]にiが素数のときtrue、素数でないときfalseを格納します。

ソースコード

int N;

boolean[] isPrime = new boolean[N];
Arrays.fill(isPrime, true);
isPrime[0] = isPrime[1] = false;
for (int i = 2; i < isPrime.length; ++i) {
	if (!isPrime[i])
		continue;
for (int j = 2 * i; j < isPrime.length; j += i) {
		isPrime[j] = false;
	}
}