Lesson 11 · Core algorithms

Prime Numbers and the Sieve of Eratosthenes

Trial division answers one primality query; the Sieve of Eratosthenes preprocesses an entire range. Every composite has a prime factor at most its square root, which explains both stopping rules.

Testing One Number

A prime is an integer greater than 1 divisible only by 1 and itself. 1 is not prime — a convention rather than an accident, adopted so that factorisation into primes is unique; if 1 were prime, every number would have infinitely many factorisations. 2 is prime, and is the only even prime.

The obvious test divides n by every integer from 2 to n−1, at O(n). It can be cut immediately.

Divisors come in pairs. If d divides n, so does n/d, and one member of each pair is at most √n. So a divisor larger than √n implies a matching one smaller, which would already have been found. Checking up to √n is therefore sufficient, giving O(√n) — for a number near 10¹², that is a million operations instead of a trillion.

Write the loop condition as i * i <= n rather than i <= sqrt(n). The floating-point square root can round incorrectly at large values, and the integer multiplication is both exact and usually faster. On the edge of the 64-bit range, i * i can itself overflow, in which case i <= n / i is the safe form.

A further halving: after testing 2 explicitly, only odd divisors need checking, since any even divisor implies divisibility by 2. Extending this to skip multiples of 3 as well — testing 2, 3, then numbers of the form 6k ± 1 — cuts the work by another third, since every prime above 3 has that form.

For genuinely large numbers, deterministic trial division becomes impractical and probabilistic tests take over. Miller–Rabin tests a number in O(k log³ n) with an error probability falling exponentially in the number of rounds k, and with fixed well-chosen bases it is deterministic for all 64-bit integers. This is what cryptographic libraries use, since RSA needs primes of hundreds of digits.

1 is not prime, so that factorisation stays unique
Divisors pair up around √n, so testing to √n suffices
Use i * i <= n, not a floating-point square root
Miller–Rabin handles the sizes trial division cannot

Sieving a Whole Range

When every prime up to n is wanted, testing each number separately costs O(n√n). The Sieve of Eratosthenes does the whole range in O(n log log n) — close enough to linear that the difference is negligible in practice.

It works by elimination rather than testing. Create a boolean array of size n+1, initially all true, and mark 0 and 1 as not prime. Then for each i from 2 upward: if i is still marked prime, mark all its multiples as composite. When the loop finishes, everything still marked is prime.

Two optimisations are standard and both are worth being able to justify.

Start marking from i², not from 2i. Any smaller multiple of i — say k·i for k < i — has a factor k smaller than i, and was therefore already marked when k's own multiples were processed. Beginning at i² skips work that is provably redundant.

Stop the outer loop at √n. If i exceeds √n, then i² exceeds n and there is nothing left in range to mark. Every composite up to n has a factor at most √n, so all of them have already been eliminated by that point.

The correctness argument is short and is what an exam answer needs. Every composite number has at least one prime factor ≤ its square root. So every composite in the range is a multiple of some prime the sieve processes, and gets marked. Nothing prime is ever marked, since a prime has no factor other than 1 and itself, and the sieve only marks proper multiples. Therefore unmarked exactly equals prime.

The complexity comes from summing n/p over all primes p up to n. That sum is n · Σ(1/p), and the sum of reciprocals of primes grows as log log n — a result of Mertens — giving O(n log log n). For n = 10⁶, log log n is under 3.

Mark multiples of each surviving number; unmarked means prime
Start marking at i², since smaller multiples were already handled
Stop the outer loop at √n — every composite has a factor below it
O(n log log n), from the sum of prime reciprocals

Memory, and the Sieve's Variants

The sieve's real constraint is memory, not time. A boolean array up to 10⁸ is 100 MB even at one byte per entry, and languages that use a full word per boolean are worse.

Odd-only sieving halves it immediately: after handling 2 separately, store only odd numbers, mapping value v to index v/2. Same algorithm, half the space, and slightly better cache behaviour.

A bitset stores eight values per byte, cutting memory another eightfold. Combined with odd-only storage, a sieve to 10⁹ becomes feasible in about 60 MB. The cost is bit manipulation on every access, which is a small constant factor.

A segmented sieve removes the memory limit entirely for large ranges. Sieve the primes up to √n conventionally, then process the range in blocks that fit in cache, marking each block's multiples using those base primes. This gives the primes in an arbitrary high range — say between 10¹² and 10¹² + 10⁶ — without ever allocating an array of size 10¹². It is also faster than a plain sieve at large n, because each block stays in cache instead of thrashing main memory.

The linear sieve, or sieve of Euler, achieves O(n) by ensuring each composite is marked exactly once, by its smallest prime factor. Plain Eratosthenes marks 12 three times — as a multiple of 2, and via 3, and so on. The linear sieve avoids the repetition and, more usefully, records each number's smallest prime factor, which makes factorising any number in the range an O(log n) walk rather than a fresh trial division.

That side benefit is often the real reason to use it. A sieve storing smallest prime factors answers factorisation, divisor counts, and Euler's totient for every number in the range, which is what most problems built on a sieve actually need.

Despite the better bound, the linear sieve is not always faster in practice — its access pattern is less cache-friendly than Eratosthenes', and for n up to about 10⁷ a well-implemented bitset Eratosthenes usually wins.

Choosing a method
Situation	Method	Cost
Test one number	Trial division to √n	O(√n)
Test one very large number	Miller–Rabin	O(k log³ n)
All primes up to n	Sieve of Eratosthenes	O(n log log n)
Primes in a high range	Segmented sieve	O((r−l) log log r)
Need factorisation too	Linear sieve (smallest prime factor)	O(n) build, O(log n) per factorisation
Many queries below n	Sieve once, then O(1) lookup	O(n log log n) once

Odd-only storage halves memory; a bitset cuts it eightfold again
Segmented sieving handles high ranges and stays in cache
The linear sieve is O(n) and records smallest prime factors
Eratosthenes with a bitset often still wins below ~10⁷

Implementation

Strike composite multiples through 30

n = 30
prime = [True] * (n + 1)
prime[0] = prime[1] = False
p = 2

while p * p <= n:
    if prime[p]:
        for x in range(p * p, n + 1, p):
            prime[x] = False
    p += 1

print("Primes:", ", ".join(str(i) for i in range(2, n + 1) if prime[i]))

#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <functional>
#include <tuple>
#include <array>
#include <numeric>
using namespace std;
int main() {
    int n=30;
    vector<bool>p(n+1,true);
    p[0]=p[1]=false;
    for(int x=2;x*x<=n;x++)if(p[x])for(int y=x*x;y<=n;y+=x)p[y]=false;
    cout<<"Primes: ";
    bool first=true;
    for(int i=2;i<=n;i++)if(p[i]) {
        if(!first)cout<<", ";
        cout<<i;
        first=false;
    }
}

import java.util.*;
class Main {
    public static void main(String[]z) {
        int n=30;
        boolean[]p=new boolean[n+1];
        Arrays.fill(p,true);
        p[0]=p[1]=false;
        for(int x=2;x*x<=n;x++)if(p[x])for(int y=x*x;y<=n;y+=x)p[y]=false;
        System.out.print("Primes: " );
        boolean first=true;
        for(int i=2;i<=n;i++)if(p[i]) {
            if(!first)System.out.print(", " );
            System.out.print(i);
            first=false;
        }
    }
}

Watch it run

Step through it

Running on N=30

Output

Read all 15 Steps

Create candidates Assume positions 2 through 30 may be prime.
Exclude zero and one Zero and one do not meet the definition.
Select prime 2 Two is still unmarked, so it is prime.
Start at 2² Earlier multiples do not exist for two; marking begins at four.
Strike even multiples Mark 4,6,8,…,30 composite.
Advance to 3 Three survived and is prime.
Start at 3² Six was already handled by two, so begin at nine.
Strike multiples of 3 Mark 9,12,15,18,21,24,27,30.
Skip composite 4 Four is marked, so it gets no marking pass.
Advance to prime 5 Five survived and is prime.
Start at 5² 10,15,20 were handled earlier; begin at 25.
Strike multiples of 5 Mark 25 and 30.
Stop after √30 The next candidate is above √30, so every remaining composite already has a processed factor.
Collect survivors Read every true position from 2 onward.
Return primes Ten primes remain.

Choosing, and the Traps

The decision is governed by how many numbers you need to classify.

One number, or a handful — use trial division to √n. Building a sieve costs O(n) memory and time to answer a single question, which is wasteful unless n is small.

Every prime up to n, or many queries in that range — sieve once, then each query is an O(1) array lookup. The break-even is roughly when the number of queries approaches √n, since that is where the repeated trial divisions begin to exceed the sieve's build cost.

A high, narrow range — segmented sieve. Factorisation of many numbers — linear sieve storing smallest prime factors. Cryptographic sizes — Miller–Rabin; nothing deterministic is feasible there.

Several errors recur and are worth checking for explicitly.

Off-by-one in the array size. A sieve for primes up to and including n needs n+1 entries, since indices run 0 to n. Allocating n silently excludes n itself.

Forgetting 0 and 1. Both must be marked non-prime explicitly; the marking loop never touches them, so they stay true and are reported as prime.

Overflow at i². For n near the 32-bit limit, i * i overflows before the comparison, and the loop terminates early or runs forever depending on the sign. Use a wider type or compare i <= n / i.

Marking from 2i instead of i² is correct but does redundant work; stopping the outer loop at n instead of √n is likewise correct but wasteful. Neither breaks the answer, which is why they survive testing — they only cost time.

A final note worth stating: primes thin out but never run out. Euclid proved there are infinitely many, and the prime number theorem says the count below n is approximately n / ln n — so about 78,498 primes below a million, roughly 7.8% density. That estimate is useful for sizing an output array before sieving.

Few queries: trial division. Many, or a whole range: sieve once
Allocate n+1 entries and mark 0 and 1 non-prime explicitly
Guard i * i against overflow near the type's limit
About n / ln n primes below n — useful for sizing the output