Algorithm

boolean[] sieve(int n) {
  boolean[] isPrime = new boolean[n + 1];
  Arrays.fill(isPrime, true);
  isPrime[0] = isPrime[1] = false;
  for (int i = 2; (long)i * i <= n; i++)
    if (isPrime[i])
      for (int j = i * i; j <= n; j += i) isPrime[j] = false;
  return isPrime;
}
Advertisement

Start at i²

Smaller multiples already marked by smaller primes. Saves time.

Advertisement

Linear sieve

Each composite marked exactly once by its smallest prime factor. Slightly faster, O(N).

Segmented sieve

Sieve one segment at a time. Handles N ≥ 10¹² without O(N) memory.