Prime Sieve
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.
The Prime Sieve precomputes all primes up to a limit in one pass instead of checking each number independently. The rest of this chapter covers the trial-division primality test, the Sieve of Eratosthenes, and the Smallest Prime Factor (SPF) sieve for fast prime factorization.
What Makes a Number Prime?
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:
- 1 is not a prime number (by definition).
- 2 is the only even prime. Every other even number is divisible by 2.
- If a number n has no divisors up to sqrt(n), it is prime. If
n = a · band bothaandbare greater than sqrt(n), thena · b > n, which is a contradiction.
This leads to two fundamentally different approaches: checking one number at a time (trial division) versus generating all primes up to a limit (sieving). The diagram below previews what the sieve does. Every composite is annotated with the smallest prime that crosses it off, while primes stay green.
Green nodes are prime. Red nodes are even composites crossed off when p = 2. Orange nodes (9 here) are odd composites whose smallest prime factor is ≥ 3; they survive the p = 2 pass and get crossed off by a later prime.
Approach 1: Trial Division (Brute Force Primality Test)
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:
- If n <= 1, return false.
- If n <= 3, return true.
- If n is divisible by 2 or 3, return false.
- Check all numbers of the form 6k +/- 1 up to sqrt(n). (All primes greater than 3 are of this form.)
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.
Approach 2: Sieve of Eratosthenes
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:
- Create a boolean array
isPrime[0..n], initialized totrue. - Mark
isPrime[0]andisPrime[1]asfalse. - For each number p starting from 2:
- If
isPrime[p]istrue, then p is prime. - Mark all multiples of p (starting from p * p) as
false. - Continue until p * p > n.
- All indices still marked
trueare prime.
*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.
Approach 3: Prime Factorization Using Smallest Prime Factor (SPF) Sieve
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:
- Create an array
spf[0..n]wherespf[i] = iinitially (every number is its own smallest factor). - Run the sieve: for each prime p, set
spf[m] = pfor all multiples m of p wherespf[m]has not been updated yet (i.e.,spf[m] == m). - To factorize a number x: repeatedly divide x by
spf[x]until x becomes 1.
The straightforward factorize(x, spf) returns a flat list of prime factors with repetitions. For example, factorizing 24 gives [2, 2, 2, 3]. To get the more useful (prime, exponent) form like [(2, 3), (3, 1)], group consecutive duplicates while dividing: instead of pushing spf[x] every iteration, count how many times the current smallest prime divides x before moving on. The Implementation section below shows both variants.
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).
Example Walkthrough: Sieve of Eratosthenes for n = 30
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.
Implementation
Trial Division: isPrime
Sieve of Eratosthenes (Count Primes, LeetCode 204)
Given an integer n, return the number of primes strictly less than n.
Prime Factorization Using SPF Sieve
Grouped Variant: (prime, exponent) Pairs
The version above returns [2, 2, 2, 3] for n = 24. To get the canonical [(2, 3), (3, 1)] form, divide out the entire run of each prime before moving on:
The translation to other languages is mechanical: same outer while x > 1, an inner counter that increments while spf[x] divides x.
Complexity Analysis
| Algorithm | Time Complexity | Space Complexity | Use Case |
|---|---|---|---|
| Trial Division | O(sqrt(n)) per query | O(1) | Checking a single number |
| Sieve of Eratosthenes | O(n log log n) | O(n) | Finding all primes up to n |
| SPF Sieve (build) | O(n log log n) | O(n) | Precomputing smallest prime factors |
| SPF Factorization | O(log n) per query | O(log n) | Factorizing after sieve is built |
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.
Choosing Between the Three
The three algorithms have overlapping use cases but very different cost profiles:
- Trial division is for one-off primality checks on values that may be larger than what you can sieve. Use it when you have a single number up to roughly 10^12 (the inner loop runs up to sqrt(n) ≈ 10^6, which finishes in milliseconds).
- Sieve of Eratosthenes is for "tell me all primes up to N" or any problem that does many primality lookups on values in a fixed range. The boolean array fits comfortably in memory up to N ≈ 10^8; beyond that, switch to a bitset or segmented sieve.
- SPF sieve is for repeated factorization queries on values up to N. The build cost is the same as the regular sieve, but each factorization is O(log n) instead of O(sqrt(n)). Use it when the same number range is factorized many times (divisor counts, multiplicative-function sums, factor-of-each-element problems).
A useful rule of thumb: if the problem range fits in a sieve and you need primality or factorization for many values in that range, precompute once. If you have a single huge number outside any reasonable sieve range, fall back to trial division (and consider Pollard's rho if n > 10^14, which is beyond this chapter).