Sieve vs Trial Division
Use a sieve when you need every prime below a limit, or many primality questions over the same range, because one pass answers all of them. Use trial division for a single large number, where building a table of that size is impossible.
The two answer different questions. A sieve fills an array of size n and marks composites, so afterwards every number below n is answered in O(1) at a cost of O(n log log n) once. Trial division tests one number at a time in O(sqrt(n)) with no memory, which is the only option when n is larger than any array you could allocate.
Side by side
| Dimension | Sieve of Eratosthenes | Trial division |
|---|---|---|
| Answers | Every number below the limit | One number per call |
| Cost | O(n log log n) for the whole range | O(sqrt n) per number |
| Memory | O(n), one bit or byte per number | O(1) |
| Limit | Bounded by memory, 10 million is routine | Works on any single number that fits in a long |
| Factorisation | O(log n) per number with a smallest-prime-factor table | O(sqrt n) per number |
| Setup | One pass before any query | None |
When to pick each
Sieve of Eratosthenes
- Count or list the primes below a million, which the sieve does in milliseconds.
- Many queries over the same bounded range, where the table is built once and read repeatedly.
- Repeated factorisation, where storing the smallest prime factor per number turns each factorisation into a short chain of divisions.
Trial division
- One primality test on a number far too large to sieve, such as something near a billion.
- Factorising a single value, where stopping at the square root is enough and no table is needed.
- Memory-constrained code, since trial division allocates nothing at all.
Starting the inner loop of the sieve at 2 times i rather than i times i. Everything below i times i has already been crossed out by a smaller prime, so the extra work is pure waste and turns a near-linear algorithm into something noticeably slower. The matching slip in trial division is looping to n instead of the square root of n, which costs a factor of sqrt(n) for no benefit at all.
Questions people ask
Why does checking up to the square root suffice?
Because divisors come in pairs. If n is a times b and a is at most b, then a cannot exceed the square root of n. So any composite number has a factor at or below its square root, and finding none means there is none to find.
What is a segmented sieve for?
Primes in a high range you cannot sieve from zero, such as between a billion and a billion plus a million. You sieve the primes up to the square root of the upper bound, then use them to cross out composites in the window, which keeps memory proportional to the window rather than the limit.
Where does the smallest prime factor table help?
Repeated factorisation. A standard sieve records only whether a number is prime, while storing the smallest prime factor instead lets you factorise any number in the range by dividing it down one factor at a time, which is O(log n) per number rather than O(sqrt n).