Menu

Earn Premium with Referrals

Invite your friends and earn Premium rewards through our referral program.

See how it works and start inviting friends.

Prime Sieve
DSA

Prime Sieve

Understand how the Sieve of Eratosthenes efficiently finds all prime numbers up to a given limit.

The sieve marks every composite by crossing multiples of each prime it finds.

Its core advantage:

All primes up to n in O(n log log n) — then every primality question is O(1) lookup.

Focus on recognizing:

Many primality questions on bounded numbers = sieve once, answer free

For a single huge number, don’t sieve — trial-divide to √n.

Core Template

public boolean[] sieve(int n) {
    boolean[] isPrime = new boolean[n + 1];
    Arrays.fill(isPrime, 2, n + 1, true);

    for (int p = 2; (long) p * p <= n; p++)
        if (isPrime[p])
            for (int m = p * p; m <= n; m += p)
                isPrime[m] = false;

    return isPrime;
}
def sieve(n: int) -> list[bool]:
    is_prime = [False, False] + [True] * (n - 1)

    for p in range(2, int(n**0.5) + 1):
        if is_prime[p]:
            for m in range(p * p, n + 1, p):
                is_prime[m] = False

    return is_prime
vector<bool> sieve(int n) {
    vector<bool> isPrime(n + 1, true);
    isPrime[0] = isPrime[1] = false;

    for (int p = 2; (long long)p * p <= n; p++)
        if (isPrime[p])
            for (int m = p * p; m <= n; m += p)
                isPrime[m] = false;

    return isPrime;
}
function sieve(n) {
  const isPrime = Array(n + 1).fill(true);
  isPrime[0] = isPrime[1] = false;

  for (let p = 2; p * p <= n; p++)
    if (isPrime[p])
      for (let m = p * p; m <= n; m += p)
        isPrime[m] = false;

  return isPrime;
}

Two details carry all the performance: start at p*p, stop when p*p > n.

Pattern 1: Single Primality Check

Watch the sieve cross out composites up to 19 — evens first, then multiples of 3 — until only primes survive. Press ▶ to animate.

Sieve of Eratosthenes

Mark all primes up to n by eliminating multiples.

Start at p=2; if prime, cross out every multiple p·k. Advance p to the next number still marked prime; stop when p*p > n (smaller composites are already crossed). Remaining marks are primes.

ARRAY VISUALIZER
Steps –
2
0
3
1
4
2
5
3
6
4
7
5
8
6
9
7
10
8
11
9
12
10
13
11
14
12
15
13
16
14
17
15
18
16
19
17
Press ▶ to animate, or step through manually.
Variables
keys: ← → space F
Pseudocode

                        1
                        isPrime = [true] * n;  isPrime[0] = isPrime[1] = false
                      
                        2
                        for p from 2 while p*p <= n:
                      
                        3
                          if isPrime[p]:
                      
                        4
                            mark p*p, p*p+p, ... < n as composite
                      
                        5
                        remaining true cells are the primes ≤ n

No sieve needed — trial division to √n:

public boolean isPrime(long n) {
    if (n < 2) return false;
    for (long d = 2; d * d <= n; d++)
        if (n % d == 0) return false;
    return true;
}
def is_prime(n: int) -> bool:
    if n < 2:
        return False
    d = 2
    while d * d <= n:
        if n % d == 0:
            return False
        d += 1
    return True
bool isPrime(long long n) {
    if (n < 2) return false;
    for (long long d = 2; d * d <= n; d++)
        if (n % d == 0) return false;
    return true;
}
function isPrime(n) {
  if (n < 2) return false;
  for (let d = 2; d * d <= n; d++)
    if (n % d === 0) return false;
  return true;
}

One number → trial divide to √n. Many numbers ≤ N → sieve.

Common Mistakes

Crossing from p instead of p*p.

Multiples below p*p were already crossed by smaller primes — starting at p wastes time but still works. Starting at p*p is the idiom.

Loop condition p <= n.

You only need p * p <= n — composites above have a factor ≤ √n already processed.

Integer overflow in p * p.

In Java/C++, p * p overflows int for large p — cast to long before multiplying.

Complexity

OperationTime
Sieve to nO(n log log n)
Single checkO(√n)
SpaceO(n)

My Private Notes

Notes are auto-saved locally to this device.