Prime numbers appear in many coding interview problems, especially those involving factorization, divisibility, and number theory. A naive approach to checking primes works for small inputs, but quickly becomes too slow when constraints grow.

This is where the Prime Sieve comes in. Instead of checking each number independently, it precomputes all prime numbers up to a limit in an efficient way. This shift from repeated work to preprocessing is a common optimization pattern in interviews.

In this chapter, we will build an intuition for how the sieve works, understand why it is efficient, and learn how to apply it in problems that involve primes and factorization.

A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. The first few primes are 2, 3, 5, 7, 11, 13, 17, 19, 23, 29.

A few things to note:

This leads us to two fundamentally different approaches: checking one number at a time (trial division) versus generating all primes up to a limit (sieving).

The simplest way to check if a number n is prime is to test whether any integer from 2 to sqrt(n) divides it evenly.

Why sqrt(n)? If n has a factor larger than sqrt(n), the paired factor must be smaller than sqrt(n). So we only need to check up to the square root.

Algorithm:

This works perfectly for checking individual numbers, but if you need to find all primes up to n, calling this function for every number gives O(n * sqrt(n)) total time. That is where the sieve becomes essential.

The Sieve of Eratosthenes flips the problem on its head. Instead of checking each number individually, we start by assuming every number is prime, then systematically eliminate the composite ones.

Algorithm:

Why start marking from p * p?

Because all smaller multiples of p (like 2p, 3p, ..., (p-1) * p) have already been marked as composite by smaller primes. For example, when p = 5, we do not need to mark 10 (already handled by 2), 15 (already handled by 3), or 20 (already handled by 2). We start directly at 25.

A powerful variation of the sieve precomputes the smallest prime factor for every number. Once you have this, you can factorize any number up to n in O(log n) time by repeatedly dividing by the smallest prime factor.

Algorithm:

This is especially useful when you need to factorize many numbers. Building the SPF sieve is O(n log log n), and each factorization is O(log n).

Let us trace through the algorithm step by step. We start with all numbers from 2 to 30 marked as prime (T = true).

Step 1: p = 2 (prime). Mark multiples starting from 2*2 = 4: cross off 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30.

Step 2: p = 3 (still marked prime). Mark multiples starting from 3*3 = 9: cross off 9, 15, 21, 27. (Note: 6, 12, 18, 24, 30 were already crossed off by 2.)

Step 3: p = 4 (marked false). Skip it.

Step 4: p = 5 (still marked prime). Mark multiples starting from 5*5 = 25: cross off 25. (30 is already crossed off.)

Step 5: p = 6 (stop). Since 6*6 = 36 > 30, we are done.

Primes up to 30: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29. That is 10 primes.

Notice how few steps it took. We only needed to sieve with p = 2, 3, and 5. The sqrt(30) boundary means we stop early, and the p*p starting point means we skip redundant work.

Trial Division: isPrime

Given an integer n, return the number of primes strictly less than n.

Why O(n log log n) for the sieve? The total number of composite markings is:

n/2 + n/3 + n/5 + n/7 + ... (sum over all primes p <= n)

By Mertens' theorem, the sum of reciprocals of primes up to n is approximately log(log(n)). Multiplying by n gives O(n log log n). In practice, this is nearly linear. For n = 10 million, log(log(n)) is about 3.