The sieve of Eratosthenes, and how to make it fast Image: Ricordisamoa, Wikimedia Commons (public domain)

The sieve of Eratosthenes, and how to make it fast

Eratosthenes of Cyrene, who ran the library of Alexandria in the third century BC and measured the circumference of the Earth to within a few percent, is credited with the simplest method ever found for listing primes. Write the integers from 2 to N. Circle 2 and cross out every second number after it. Circle the next number not crossed out, which is 3, and cross out every third number after it. Circle 5, cross out every fifth. Continue. Every circled number is prime and every crossed-out number is composite, because a number gets crossed out exactly when a smaller prime divides it.

Why it stops at the square root

The first improvement is one that Eratosthenes may well have known. If N = 100, you only need to cross out the multiples of 2, 3, 5, and 7. After that, every number up to 100 that is still standing is prime, with no more work.

The reason is that a composite number n has a prime factor no larger than its square root. If n = ab with both factors greater than 1, they cannot both exceed the square root of n, since then their product would exceed n. So the smaller factor is at most the square root, and the smallest prime factor is smaller still. Any composite number up to 100 therefore has a prime factor at most 10, which means at most 7, and crossing out the multiples of 2, 3, 5, and 7 catches all of them. The same argument shows that when you cross out the multiples of a prime p, you can start at p² rather than at 2p, because every smaller multiple of p has a smaller prime factor and has been crossed out already.

The rule has a second use that has nothing to do with sieving: to test whether a single number is prime by trial division, you need only try the primes up to its square root. To check 10007, try the 25 primes up to 97. None divides it, so 10007 is prime.

Counting the work

How many crossings-out does the sieve make up to N? For each prime p up to the square root of N, about N/p of them. The sum of 1/p over the primes up to x grows like ln ln x, a fact that goes back to Euler and is proved in Unit 12 of the masterclass, so the total is about N ln ln N. For N = 10⁹ the factor ln ln N is about 3, and the sieve does roughly three billion simple operations, which a modern processor finishes in a few seconds. The sieve is, to within that slowly growing factor, as fast as merely writing the numbers down. No method is known that lists all the primes up to N much faster, and there is a sense in which none can exist, since the output alone has about N / ln N entries.

The problem with memory

The naive sieve keeps one bit, or more often one byte, for every integer up to N. For N = 10⁹ that is a gigabyte of bytes or 125 megabytes of bits; for N = 10¹² it is a terabyte or 125 gigabytes, and the whole array has to be swept once for every prime up to a million. That is where the simple version runs out of steam, and the remedy is the segmented sieve.

Instead of sieving the whole range at once, sieve it in blocks of, say, a few hundred thousand numbers, small enough to fit in the processor's fastest memory. For each block, you need to cross out the multiples of every prime up to the square root of N that fall inside the block. Those primes are found first by an ordinary sieve up to the square root, which for N = 10¹² means up to a million, a trivial job. Then for each block and each sieving prime, compute the first multiple in the block and step through. The total amount of crossing-out is the same as before, but the memory is tiny and the processor never waits for data. This is the method of the programs that hold the counting records: Kim Walisch's primesieve counts the primes below 10¹² in a handful of seconds on a laptop, and the verification of Goldbach's conjecture to 4 × 10¹⁸ by Oliveira e Silva, Herzog, and Pardi used a segmented sieve on and off for about a decade.

The wheel

A second improvement removes the smallest primes from the array altogether. Every prime above 3 leaves remainder 1 or 5 on division by 6, since the other residues are divisible by 2 or 3. So the array need only store the numbers of those two forms, a third of the integers, and the sieving by 2 and 3 disappears. Extending to the primes 2, 3, and 5 leaves 8 residues out of 30; with 7 as well, 48 out of 210. This is called a wheel, because the pattern of candidate residues repeats with period 30 or 210 like the spokes of a wheel rolling along the number line. Each extra prime in the wheel buys less than the last, and practical sieves stop at 30 or 210.

Combined, the segmented sieve with a wheel runs about ten times faster than the version a beginner writes, and it is a good project after Unit 3 of the masterclass: write the naive sieve in Python, time it to 10⁷, then segment it and watch the memory fall and the speed rise.

Sieving without listing

Counting the primes is a different problem from listing them, and it can be done faster. The number of primes below 10²⁵ is known, 176,846,309,399,143,769,411,680, and nobody has ever listed them; there are too many to store on all the computers in the world. The count comes from a method that Meissel used by hand in the 1870s and Lehmer mechanized in the 1950s, refined by Lagarias, Miller, and Odlyzko in 1985 and by Deléglise and Rivat in 1996. The idea is inclusion and exclusion: the number of integers up to x with no prime factor below y can be written as a sum over the divisors of the product of those primes with Möbius signs, and the sum is tamed by clever grouping. The same formula, written out in Unit 15 of the masterclass, is the starting point of the sieve methods of Brun and Selberg, which count primes in sets where nobody can list them, such as twin primes or Goldbach pairs.

Eratosthenes in the research literature

The sieve as an idea, as opposed to an algorithm, is the subject of the last units of this masterclass. The formula behind the sieve of Eratosthenes, with inclusion and exclusion, gives an exact count of the primes up to x once you know the primes up to the square root. Try to use it to estimate π(x) rather than compute it and it fails badly, because the number of terms is 2 to the power of the number of sieving primes and the rounding errors swamp the answer. Viggo Brun's insight in 1915 was to stop the inclusion and exclusion early and accept an inequality rather than an equation. Atle Selberg's in 1947 was to replace the Möbius signs by a cleverly chosen quadratic form. Those ideas led to Chen's theorem of 1973, that every large even number is the sum of a prime and a number with at most two prime factors, and to the bounded gaps between primes of Zhang and Maynard in 2013. All of it is, in the end, a sophisticated way of crossing out multiples.

Unit 3 of the masterclass, free to read as the sample unit, works through the sieve up to 100 step by step and explains the square root rule; Unit 15 writes the sieve as a formula and shows where the formula leads.

Study the integers properly

The NT Masterclass: weekly units, quizzes, a final exam, and a certificate.
About the program
Keep reading

Related articles