Skip to content
Tutorials Center
My learning

Topics

Lesson 187 of 225 ยท Math and Bit Manipulation

Sieve of Eratosthenes, Segmented Sieve and Miller-Rabin

Generate primes with the sieve of Eratosthenes, extend it with a segmented sieve for huge ranges, and test big numbers with the Miller-Rabin primality test in Python.

Primes show up everywhere in algorithm problems: counting them, factoring numbers, hashing, cryptography. The basic idea, testing divisors one by one, works for small numbers but collapses when you need every prime below ten million, or when you must decide whether a 60-bit number is prime. Two different tools solve those two different jobs.

If you want all primes up to a limit, use a sieve. If you want to test one huge number, use the Miller-Rabin test. This lesson builds both, plus the segmented sieve that handles ranges too large for ordinary memory. The earlier number theory basics lesson introduced the simple sieve; here we make it fast and go much further.

Why trial division is not enough

To test whether n is prime, try every divisor d with d * d <= n. If none divides n, it is prime. That costs up to โˆšn steps for one number. Testing all numbers up to N this way costs about NโˆšN steps, which is hopeless for N = 10โท.

The sieve avoids repeating work. Instead of asking "is 91 divisible by anything?" for each number, it asks the reverse question once: "which numbers are multiples of 7?" and crosses them all out.

The sieve of Eratosthenes

Start with a table where every number from 2 to N is marked "maybe prime". Take the smallest unmarked number, p. It must be prime, because nothing smaller divided it. Cross out its multiples. Repeat with the next unmarked number.

Two optimizations make it fast:

  1. Start crossing out at p * p. Smaller multiples like p * 2 or p * 3 were already crossed out by the smaller primes 2 and 3.
  2. Stop when p * p > N. Any composite number up to N has a prime factor at most โˆšN, so everything left is prime.
flowchart TD
    A["Mark 2..N as prime"] --> B["p = 2"]
    B --> C{"p * p <= N ?"}
    C -- "no" --> F["Every number still marked is prime"]
    C -- "yes" --> D{"p still marked?"}
    D -- "yes" --> E["Cross out p*p, p*p+p, p*p+2p, ..."]
    D -- "no" --> G["p = p + 1"]
    E --> G
    G --> C

The sieve loop: only primes up to โˆšN cross out multiples, starting at their own square.

In Python a bytearray is a compact table (one byte per number), and slice assignment crosses out all multiples in one fast operation.

Python A fast sieve with a bytearray

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The cost is O(N log log N) time, which is very close to linear, and O(N) memory. For N = 10โถ that is a fraction of a second even in Python.

Smallest prime factor sieve

A small change gives you far more than a yes/no table. Store, for each number, its smallest prime factor (SPF). Then you can factor any number up to N by repeatedly dividing by its SPF, in O(log n) steps per number.

Python Factor many numbers with a smallest-prime-factor table

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

When a problem has many queries such as "how many divisors does x have?", build this table once and each query becomes nearly free.

The segmented sieve

Suppose you need the primes between 10ยนยฒ and 10ยนยฒ + 1000. A plain sieve would need a table of a trillion entries. But you only want a tiny window, and a composite number in that window must have a prime factor at most โˆš(10ยนยฒ) = 10โถ.

So: sieve the small primes up to โˆšhi once, then use them to cross out multiples inside the window only. Memory is O(โˆšhi + window size).

For each small prime p, the first multiple of p that is at least lo is max(p * p, ((lo + p - 1) // p) * p). Starting from p * p protects p itself when the window contains a small prime.

Python Primes in a window, without a giant table

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

If you must process a very large range, split it into many windows of, say, a million numbers each and run the same routine on each window. That keeps memory small and also fits the CPU cache.

Testing one big number: Miller-Rabin

Sieves are useless when you hold a single huge number such as 2โถยน โˆ’ 1. Trial division would need about 1.5 billion steps. We need a test that runs in time polynomial in the number of digits.

A tempting idea is Fermat's test: if p is prime, then a^(p-1) % p == 1 for every a not divisible by p. Composite numbers usually fail it. Unfortunately some composites, the Carmichael numbers like 561, pass for every base coprime to them.

Miller-Rabin strengthens the test. Write n - 1 = d * 2^s with d odd. For a base a, compute x = a^d mod n. If n is prime, then one of these must be true:

  • x is 1 or n - 1, or
  • squaring x up to s - 1 times produces n - 1 at some point.

If neither holds, a is a witness that n is composite. This works because in a prime field the only square roots of 1 are 1 and โˆ’1, so a chain that reaches 1 without passing through โˆ’1 exposes a composite.

flowchart TD
    S["n - 1 = d * 2^s, d odd"] --> X["x = a^d mod n"]
    X --> Q1{"x is 1 or n-1 ?"}
    Q1 -- "yes" --> PASS["a passes: n looks prime"]
    Q1 -- "no" --> L["square x, up to s-1 times"]
    L --> Q2{"x became n-1 ?"}
    Q2 -- "yes" --> PASS
    Q2 -- "no" --> FAIL["a is a witness: n is composite"]

One Miller-Rabin round for a single base a.

Each base catches at least 75% of composites, so a few random bases make the error tiny. Better still, for numbers below 3.3 ร— 10ยฒโด a fixed set of bases (the first twelve primes, 2 to 37) gives a fully deterministic answer. That covers every 64-bit integer.

Python Deterministic Miller-Rabin

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

pow(a, d, n) is built-in modular exponentiation (see fast exponentiation), so each round costs O(log n) multiplications. With 12 bases the whole test is a few hundred operations even for a 64-bit input.

Other sieves: linear, Sundaram and Atkin

The ordinary sieve crosses off some composites more than once (30 is hit by 2, 3 and 5). The linear sieve guarantees that every composite is written exactly once, by its smallest prime factor, which makes it O(N) and gives the SPF table as a by-product. The trick: for each i, walk over the primes p found so far, mark i * p, and stop as soon as p reaches the smallest prime factor of i.

Two older curiosities follow the same job in different ways. Sundaram's sieve removes every number of the form i + j + 2ij from a list of 1..k; each survivor m gives the odd prime 2m + 1. The sieve of Atkin toggles candidates using quadratic forms (4x^2 + y^2, 3x^2 + y^2, 3x^2 - y^2) and then removes multiples of squares. It has a better asymptotic bound, but a larger constant, so in Python and most other languages a tuned Eratosthenes wins. All four give identical output.

Python Linear, Sundaram and Atkin sieves agree with Eratosthenes

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The number of writes equals the number of composites: each was marked exactly once. In practice the linear sieve is useful when you need the SPF table or other multiplicative functions (Euler's totient, the Moebius function) for all numbers up to N, since each value can be computed from the one at i while it is being marked.

Choosing between the tools

Task Best tool Cost
All primes up to N (N up to ~10โท in Python) Sieve of Eratosthenes O(N log log N)
Factor many numbers up to N SPF sieve O(log n) per query
Primes in [lo, hi] with hi huge, window small Segmented sieve O((hi-lo) log log + โˆšhi)
Is this single large number prime? Miller-Rabin O(k logยณ n)
Is this small number prime, once? Trial division O(โˆšn)

Common mistakes

  • Starting the inner loop at 2 * p. It works but repeats work. Start at p * p.
  • Off-by-one on the limit. Use limit + 1 for the table size so index limit exists, and use p * p <= limit.
  • Forgetting 0 and 1 are not prime. Clear them explicitly.
  • Using too few bases in Miller-Rabin. Bases 2, 3, 5, 7 alone are fooled by 3,215,031,751. Use the full set of twelve primes for 64-bit inputs.
  • Using Python lists of booleans for huge sieves. A list costs 8 bytes per entry; a bytearray costs 1 and is faster to slice.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Why does the sieve of Eratosthenes start crossing out multiples of p at p * p?

    A multiple k * p with k < p has a prime factor smaller than p, so an earlier pass already removed it.
  2. 2. How many primes are there up to 1,000,000?

    There are 78,498 primes below one million, a figure the sieve example prints.
  3. 3. A segmented sieve for the window [lo, hi] needs small primes up to which bound?

    Any composite number up to hi has a prime factor of at most sqrt(hi), so those primes are enough to cross out every composite.
  4. 4. What makes Miller-Rabin stronger than the plain Fermat test?

    Checking the square-root-of-one structure exposes composites such as 561 that fool every Fermat base.
  5. 5. Which tool should you use to decide whether the single number 2**61 - 1 is prime?

    A sieve or SPF table would need about 2.3 quintillion entries; Miller-Rabin needs only a few modular exponentiations.

Summary

  • A sieve crosses out multiples of each prime, starting at p * p, and finds all primes up to N in O(N log log N).
  • Store the smallest prime factor per number to factor any value up to N in O(log n).
  • A segmented sieve finds primes in [lo, hi] using only the primes up to โˆšhi and a window-sized table.
  • Miller-Rabin tests one large number using modular exponentiation; the first twelve primes as bases are exact for all 64-bit values.
  • Fermat's test is fooled by Carmichael numbers; Miller-Rabin is not.

Next: Chinese Remainder Theorem and Modular Inverse