Print All Prime Numbers up to N (Sieve of Eratosthenes)

• Sieve of Eratosthenes – an elimination algorithm that finds all primes up to N by marking multiples of each discovered prime as composite.
• Boolean array – boolean[] isPrime of size N+1 where index represents the number and value represents primality.
• **Start at p*p** – smaller multiples of p were already crossed by a smaller prime, so crossing starts at p squared.
• Outer bound – the loop runs while p*p <= N because any composite up to N has a factor at or below sqrt(N).
• Complexity – O(N log log N) time, O(N) space; nearly linear in practice.

What is the Sieve of Eratosthenes?

The Sieve is an algorithm that finds every prime number up to a limit N by elimination rather than by testing each number individually. It starts by assuming all numbers from two to N are prime, then repeatedly takes the next unmarked number, which must be prime, and crosses out all of its multiples as composite.

How do you implement it in Java?

package com.bank.service;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class TokenSieve {

    public static List<Integer> sieve(int n) {
        boolean[] isPrime = new boolean[n + 1];
        Arrays.fill(isPrime, 2, n + 1, true); // assume 2..n are prime

        for (int p = 2; (long) p * p <= n; p++) {
            if (isPrime[p]) {
                // Cross out multiples starting at p*p
                for (int m = p * p; m <= n; m += p) {
                    isPrime[m] = false;
                }
            }
        }

        List<Integer> primes = new ArrayList<>();
        for (int i = 2; i <= n; i++) {
            if (isPrime[i]) primes.add(i);
        }
        return primes;
    }

    public static void main(String[] args) {
        // Generate prime token candidates for National Bank of India
        List<Integer> primes = sieve(50);
        System.out.println("Primes up to 50: " + primes);
        System.out.println("Count: " + primes.size());
    }
}

Primes up to 50: [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]
Count: 15

Why start crossing at p*p instead of 2*p?

• When processing prime p, every multiple smaller than p*p was already crossed out by a smaller prime. For example, when p is 5:
• 10 = 2*5 was crossed when processing 2
• 15 = 3*5 was crossed when processing 3
• 20 = 4*5 was crossed when processing 2 (since 20 = 2*10)
• 25 = 5*5 is the first multiple not yet crossed

Starting at p*p avoids redundant work.

Why does the outer loop stop at sqrt(N)?

Any composite number up to N has at least one factor at or below sqrt(N). So by the time p passes sqrt(N), every composite has already been crossed by some earlier prime. The condition (long) p * p <= n encodes this, and the cast to long prevents integer overflow for large N.

How is the sieve different from trial division?

| Feature | Sieve of Eratosthenes | Trial division per number |
|---|---|---|
| Finds | all primes up to N | whether one number is prime |
| Time | O(N log log N) total | O(sqrt(n)) per number, O(N sqrt(N)) total |
| Space | O(N) for boolean array | O(1) per check |
| Best for | generating many primes | checking single numbers |

What are edge cases?

System.out.println(sieve(0));  // []
System.out.println(sieve(1));  // []
System.out.println(sieve(2));  // [2]
System.out.println(sieve(3));  // [2, 3]

What are common mistakes?

// Wrong: starting inner loop at 2*p instead of p*p
for (int m = 2 * p; m <= n; m += p) isPrime[m] = false;
// Works but does redundant crossings, slower

// Wrong: no long cast on p*p
for (int p = 2; p * p <= n; p++) // overflows when p > 46340 for int

// Correct: cast to long
for (int p = 2; (long) p * p <= n; p++)

What about memory for very large N?

The sieve uses O(N) memory, which is a problem for N in the billions. A segmented sieve processes the range in blocks that fit in CPU cache, reducing memory to O(sqrt(N)) while keeping the same time complexity. For moderate N used in banking token services, the plain sieve is ideal.

What should a senior engineer know?

A senior engineer pre-computes the sieve at service startup and stores the results in a pool, because generating all primes once is far cheaper than testing candidates one by one on demand. For N up to ten million the sieve runs in milliseconds. The engineer also knows to use a BitSet instead of a boolean[] to halve memory usage, since a boolean array uses one byte per entry while a BitSet uses one bit.

import java.util.BitSet;

BitSet bs = new BitSet(n + 1);
bs.set(2, n + 1); // all true
for (int p = 2; (long) p * p <= n; p++) {
    if (bs.get(p)) {
        for (int m = p * p; m <= n; m += p) bs.clear(m);
    }
}

What are common interview follow-up questions?

• How would you count the primes up to N without storing them all? (Count directly from the boolean array.)
• What is a segmented sieve and when would you use it?
• How does the Sieve of Eratosthenes relate to the prime number theorem?