boolean[] sieve(int n) {
boolean[] prime = new boolean[n + 1];
Arrays.fill(prime, true);
if (n >= 0) prime[0] = false;
if (n >= 1) prime[1] = false;
for (int p = 2; p * p <= n; p++) if (prime[p]) {
for (int x = p * p; x <= n; x += p) prime[x] = false;
}
return prime;
}
def sieve(n: int) -> list[bool]:
prime = [True] * (n + 1)
if n >= 0:
prime[0] = False
if n >= 1:
prime[1] = False
p = 2
while p * p <= n:
if prime[p]:
for x in range(p * p, n + 1, p):
prime[x] = False
p += 1
return prime
def sieve(n: Int): Array[Boolean] =
val prime = Array.fill(n + 1)(true)
if n >= 0 then prime(0) = false
if n >= 1 then prime(1) = false
var p = 2
while p * p <= n do
if prime(p) then
for x <- p * p to n by p do prime(x) = false
p += 1
prime
std::vector<bool> sieve(int n) {
std::vector<bool> prime(n + 1, true);
if (n >= 0) prime[0] = false;
if (n >= 1) prime[1] = false;
for (int p = 2; p * p <= n; p++) if (prime[p]) {
for (int x = p * p; x <= n; x += p) prime[x] = false;
}
return prime;
}