Number Sieves — Volume 2 — Prime Numbers and the Sieve of Eratosthenes

2.1 About This Volume

Every machine in this series descends from one procedure: the Sieve of Eratosthenes, a method for listing the prime numbers by crossing out everything that is not one. This volume is about that procedure and about the numbers it finds. It starts with what a prime is and why there is no largest one; meets Eratosthenes of Cyrene and Nicomachus of Gerasa, the writer through whom the sieve actually reached us; works the sieve step by step on the numbers 1 to 100 and explains its two efficiency rules (start each prime’s crossing at its square; stop at the square root); counts the work it does; and then uses the sieve’s output to look at the large-scale behaviour of the primes — the prime number theorem, prime gaps, twin primes, Mersenne primes and the Ulam spiral. A paper-and-pencil exercise in the middle sieves the hundred numbers from 101 to 200, and in doing so quietly introduces the idea of a segmented sieve that Volume 3 develops.

No mathematics beyond multiplication is assumed.

2.2 What a Prime Is

A prime number is a whole number greater than 1 that cannot be split into a product of two smaller whole numbers. Its only divisors are 1 and itself. The first few are

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97 …

Every whole number greater than 1 that is not prime is composite: it can be written as a product of smaller numbers, as 91 = 7 × 13 or 100 = 2 × 2 × 5 × 5. The number 1 is neither; by convention it is excluded from the primes, because including it would ruin the most important fact about them.

That fact is the fundamental theorem of arithmetic: every whole number greater than 1 can be written as a product of primes in exactly one way, apart from the order of the factors. 360 is 2 × 2 × 2 × 3 × 3 × 5 and nothing else. The primes are therefore the atoms of multiplication — every whole number is built from them, uniquely — and factoring a number means finding its atoms. (If 1 were a prime, 360 could also be written 1 × 2 × 2 × 2 × 3 × 3 × 5, or with any number of extra 1s, and the uniqueness would be lost.)

The number 2 is the only even prime, since every other even number is divisible by 2. That makes 2 the “oddest” prime, and it is why so many sieve tricks begin by setting the even numbers aside.

2.2.1 There is no largest prime

The primes thin out as the numbers grow — a quarter of the numbers up to 100 are prime, but only about one in fifteen up to ten million — and a natural question is whether they eventually stop altogether. They do not. The proof is in Euclid’s Elements, Book IX, Proposition 20, written around 300 BC (Euclid IX.20, D. E. Joyce’s edition), and it remains one of the shortest and most admired arguments in mathematics.

Suppose someone claims to have a complete list of the primes: p₁, p₂, …, pₖ. Multiply them all together and add 1:

Q = p₁ × p₂ × … × pₖ + 1.

Divide Q by any prime on the list and the remainder is 1, because Q is one more than a multiple of that prime. So no prime on the list divides Q. But Q is greater than 1, so it has at least one prime factor — and that prime is not on the list. The list was not complete after all. Since this works for any finite list, there are infinitely many primes.

The proof does not claim that Q itself is prime. With the list 2, 3, 5, 7, 11, 13 it gives Q = 30,031 = 59 × 509, which is composite — but both 59 and 509 are primes missing from the list, which is all the argument needs.

2.3 Eratosthenes, and the Book That Saved His Sieve

2.3.1 The scholar called “Beta”

Eratosthenes was born around 276 BC in Cyrene, a Greek city in what is now Libya, and studied in Athens before being summoned to Alexandria by Ptolemy III to succeed Apollonius of Rhodes as head of the great library (Wikipedia, “Eratosthenes”). He was a polymath on a scale unusual even for the period: he wrote on geography (he coined the word), chronology, astronomy, literary criticism and mathematics, and he is best remembered today for measuring the size of the Earth by comparing the angle of noon shadows at Alexandria and at Syene, the modern Aswan, on the day of the summer solstice. Admirers called him Pentathlos, after the all-round athlete of the Olympic pentathlon. Critics, according to the Byzantine encyclopaedia called the Suda, called him Beta — “Number Two” — because he was second-best at everything. He died in Alexandria in his early eighties, around 194 BC.

None of Eratosthenes’ mathematical writing survives intact. His treatise Platonikos, on the mathematics in Plato, is known only from extracts quoted by later authors. So the sieve that bears his name is known only second-hand.

2.3.2 Nicomachus’ Introduction to Arithmetic

The earliest surviving description of the sieve is in the Introduction to Arithmetic of Nicomachus of Gerasa (the modern Jerash, in Jordan), a Neopythagorean writer of around AD 100. In Book I, chapter 13, Nicomachus explains how to separate the odd numbers into primes and composites, and he attributes the method — which he calls the koskinon, the sieve — to Eratosthenes (Wikipedia, “Sieve of Eratosthenes”). The Greek text was edited by Richard Hoche in 1866 (archive.org scan of Hoche’s edition), and the standard English translation, by Martin Luther D’Ooge with studies by Frank Egleston Robbins and Louis Charles Karpinski, was published by the University of Michigan in 1926 (University of Michigan Press).

Nicomachus’ version differs from the modern one in two instructive ways.

• It sieves only the odd numbers. Since every even number past 2 is composite, he lists 3, 5, 7, 9, 11, … and works on those alone. That halves the work, and it is the first appearance of an idea Volume 3 develops into wheel factorisation.
• It crosses out multiples of every odd number, not just of the primes. Nicomachus strikes the multiples of 3, then of 5, then of 7, then of 9, and so on. Striking the multiples of 9 is wasted effort — they were all removed as multiples of 3 — and the modern rule of using only the numbers that have survived (that is, only the primes) is an efficiency later writers made explicit.

The book was enormously influential. It was translated into Arabic by Thābit ibn Qurra in the ninth century and adapted into Latin by Boethius, whose De institutione arithmetica carried it through the European Middle Ages. Generations of copyists added to it a drawn table of the sieve, a grid of odd numbers with the composites marked, which Nicomachus himself describes only in words. A recent survey of Greek manuscripts of Nicomachus and his commentators found forty-four such drawn sieves in thirty-five manuscripts, some headed Eratosthenes’ sieve, some with errors, one with the multiples of 11 and 13 never sieved at all (searching greek manuscripts for sieves). In 1772 Samuel Horsley published a reconstruction of the method, with the Greek, in the Philosophical Transactions of the Royal Society (JSTOR 106053).

Whether Eratosthenes invented the method or only gave it its name is not certain; the historian Hans-Joachim Waschkies has argued for the latter (Wikipedia, “Eratosthenes”). Either way, the name stuck, and the image of numbers falling through a mesh has organised the subject ever since.

2.4 The Sieve, Step by Step

Here is the procedure in its modern form, run on the numbers 1 to 100.

1. Write out the numbers from 2 to 100. (1 is not prime and takes no part.)
2. Take the first number not yet crossed out. At the start that is 2. It is prime: nothing smaller than it, other than 1, could divide it, because anything that did would have crossed it out.
3. Cross out every multiple of it, counting in steps of that number: for 2, cross out 4, 6, 8, …, 100.
4. Go back to step 2. The next number not crossed out is 3; it is prime; cross out 9, 12, 15, …. Then 5: cross out 25, 30, 35, …. Then 7: cross out 49, 56, 63, ….
5. Stop when the next uncrossed number is 11, because 11 × 11 = 121 is already past 100. Everything not crossed out is prime.

The result is the twenty-five primes below 100.

Notice how quickly the work runs out. The pass for 2 removes 49 numbers, the pass for 3 another 16, the pass for 5 another 6, and the pass for 7 only 3. After that, nothing is left to remove.

2.4.1 Why start at p²

In step 4 the crossing-out for 3 started at 9, not at 6; for 5 it started at 25, not at 10; for 7 it started at 49. The rule is: start crossing out the multiples of p at p × p.

The reason is that every smaller multiple of p has already been crossed out. Take p = 7. Its multiples below 49 are 14, 21, 28, 35 and 42 — that is, 7 × 2, 7 × 3, 7 × 4, 7 × 5 and 7 × 6. Each is 7 times a number smaller than 7, so each has a prime factor smaller than 7 (2, 3, 2, 5 and 2 respectively), and the pass for that smaller prime has already removed it. The first multiple of 7 that no smaller prime could have reached is 7 × 7.

The saving is modest — on 1 to 100, starting at p² means 104 crossings instead of 113 — but the habit matters, because it leads directly to the second rule.

2.4.2 Why stop at √N

Since the crossing-out for p starts at p², a prime whose square is bigger than N has nothing to cross out in the range. So the sieve can stop as soon as it reaches a prime p with p² > N — that is, once p passes the square root of N. Everything still uncrossed at that point is prime.

The same fact can be put the other way round: every composite number n has a prime factor no bigger than √n. If n = a × b with both a and b bigger than √n, then a × b would be bigger than √n × √n = n, a contradiction. So the smaller factor is at most √n, and one of its prime factors is smaller still. To sieve to 100, the primes up to 10 — namely 2, 3, 5 and 7 — are all that is ever needed. To sieve to a million, the primes up to 1,000 suffice; there are 168 of them.

This square-root rule appears again and again in this series. It is why the Lehmers’ factoring problems involve only small moduli, why a segmented sieve needs to keep only √N numbers in memory, and why the hand exercise below needs only the primes up to 13.

2.5 A Paper-and-Pencil Exercise: The Primes from 101 to 200

The sieve does not have to start at 1. Here is a self-contained exercise that sieves a window of numbers, using only the primes found in the first hundred. It takes about ten minutes.

Setup. Write the numbers 101 to 200 in a grid of ten rows of ten. Since √200 ≈ 14.1, only the primes 2, 3, 5, 7, 11 and 13 are needed.

The trick. For each prime p, find the first multiple of p inside the window, then stride by p from there.

Table 1 — A Paper-and-Pencil Exercise: The Primes from 101 to 200

Prime p	First multiple ≥ 101	Then cross out every p-th number
2	102	102, 104, 106, …, 200
3	102 (= 3 × 34)	102, 105, 108, …, 198
5	105	105, 110, 115, …, 200
7	105 (= 7 × 15)	105, 112, 119, …, 196
11	110 (= 11 × 10)	110, 121, 132, …, 198
13	104 (= 13 × 8)	104, 117, 130, …, 195

To find the starting point, divide 100 by p, round down, add 1 and multiply back by p: for 13, 100 ÷ 13 = 7.7, so the start is 8 × 13 = 104.

Checks along the way. The multiples of 11 and 13 are the ones most easily missed; 121, 143, 169 and 187 (= 11 × 17) are the traps, since they look prime at a glance. 169 = 13 × 13 is the only number in the window crossed out only by 13.

Answer. Twenty-one numbers survive:

101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199.

So there are 21 primes between 101 and 200, against 25 between 1 and 100 — the first glimpse of the thinning-out the prime number theorem describes. Look also at the pairs: 101 and 103, 107 and 109, 137 and 139, 149 and 151, 179 and 181, 191 and 193, 197 and 199 are all twin primes, primes two apart. And look at the longest run without a prime: from 113 to 127 there are thirteen consecutive composites, a prime gap of 14.

The exercise is also a small-scale demonstration of an important practical idea. The window 101–200 was sieved without ever writing down the numbers below 101; all that was needed was the short list of base primes up to √200 and, for each one, a starting offset. Sieving a long range in windows like this, carrying each prime’s offset from one window to the next, is the segmented sieve of Volume 3 — the form in which every serious modern prime sieve runs.

2.6 How Much Work Does the Sieve Do?

The sieve’s cost is the number of crossings-out. The pass for 2 makes about N/2 crossings, the pass for 3 about N/3, the pass for 5 about N/5, and so on for every prime up to √N. The total is roughly

N × (1/2 + 1/3 + 1/5 + 1/7 + 1/11 + …),

summed over the primes up to √N. The sum of the reciprocals of the primes grows, but extraordinarily slowly: Franz Mertens proved in 1874 that the sum over the primes up to x is approximately ln ln x + 0.2615, where ln is the natural logarithm. Up to a million the sum is about 2.887; up to ten million, about 3.041. The sieve’s running time therefore grows like N log log N (Wikipedia, “Sieve of Eratosthenes”).

Log log N is so close to constant that, for practical purposes, the sieve does a fixed handful of operations per number. Sieving to ten million takes about 23 million crossings — a little over two per number. Compare that with testing each number on its own by trial division (dividing by every prime up to its square root until a divisor is found or the list runs out): a single prime near ten million needs about 450 divisions to confirm, and there are 664,579 primes below ten million. For the job of listing all the primes in a range, nothing simple comes close to the sieve.

The catch is memory. The basic sieve needs one mark for every number in the range, so sieving to a billion needs a billion marks. Volume 3 shows how the segmented sieve and wheel factorisation remove most of that cost.

2.6.1 The sieve in a computer

In a computer the sieve is a row of bits, one per number, all initially set to “maybe prime,” and the crossing-out is a loop that clears every p-th bit. Because the loop never divides, and walks memory in regular strides, it is about as fast as anything a processor can do. (There is a famous fake: a short program, often presented as “the sieve of Eratosthenes” in functional-programming textbooks, that actually filters each number by trial division. Melissa O’Neill’s paper “The Genuine Sieve of Eratosthenes” shows that it is asymptotically slower than the real sieve and explains how to write the real one (O’Neill, Journal of Functional Programming, 2009).) A short listing appears in Volume 3.

2.7 How Many Primes Are There? The Prime Number Theorem

Run the sieve to larger and larger N and count what survives, and a pattern emerges. Write π(x) for the number of primes up to x (the Greek letter here just stands for “prime”; it has nothing to do with 3.14159…).

Table 2 — How Many Primes Are There? The Prime Number Theorem

x	π(x)	share of numbers that are prime	1 / ln x
100	25	25.0%	21.7%
10,000	1,229	12.3%	10.9%
1,000,000	78,498	7.85%	7.24%
10,000,000	664,579	6.65%	6.20%
10¹⁸	24,739,954,287,740,860	2.47%	2.41%
10²⁹	1,520,698,109,714,272,166,094,258,063	1.52%	1.50%

The values are from the On-Line Encyclopedia of Integer Sequences (OEIS A006880); the count up to 10²⁹, the largest yet computed, was announced by David Baugh and Kim Walisch in 2022 using Walisch’s open-source primecount program, which counts primes analytically rather than by listing them (Wikipedia, “Prime-counting function”).

The share of primes falls, but slowly, and it tracks 1/ln x. Carl Friedrich Gauss noticed this as a teenager, “in the year 1792 or 1793” by his own later recollection, after studying tables of primes; Adrien-Marie Legendre published a similar conjecture in 1798 and refined it in 1808 to x / (ln x − 1.08366) (Wikipedia, “Prime number theorem”). The statement that

π(x) is approximately x / ln x, with the ratio tending to 1 as x grows

is the prime number theorem. It was proved in 1896, independently, by Jacques Hadamard and Charles-Jean de la Vallée Poussin, building on Bernhard Riemann’s 1859 study of what is now called the Riemann zeta function. An “elementary” proof, using no complex analysis, was found by Atle Selberg and Paul Erdős in 1948–49.

The theorem has a memorable reading: near a number x, roughly one number in ln x is prime. Near a million, ln x ≈ 13.8, so about one number in fourteen is prime. Near 10¹⁰⁰, ln x ≈ 230, so about one in 230.

A better approximation is Gauss’s logarithmic integral Li(x), the area under the curve 1 / ln t from 2 to x. It is equivalent to x / ln x in the limit but far more accurate in practice, and the size of the error π(x) − Li(x) is controlled by the location of the zeros of Riemann’s zeta function. The Riemann hypothesis, still unproved, is equivalent to the statement that this error never grows much faster than √x. The most famous open problem in mathematics is, at bottom, a question about how evenly the Sieve of Eratosthenes leaves its survivors.

2.8 Gaps Between Primes

The prime number theorem says the average gap between consecutive primes near x is about ln x. The actual gaps scatter widely around that average.

Some patterns are easy to explain with the sieve. Every gap after the first is even, because all primes after 2 are odd. Gaps that are multiples of 6 are unusually common, because two numbers six apart are both odd and either both or neither divisible by 3, so a pair that survives the sieve for 2 and 3 together is likelier six apart than two or four apart. Below a million, 6 is by far the commonest gap.

Arbitrarily long gaps exist. For any n, the n − 1 consecutive numbers n! + 2, n! + 3, …, n! + n are all composite (the first is divisible by 2, the next by 3, and so on), so there are runs of composites as long as anyone likes. The first gap of 20 or more comes after 887 (the next prime is 907); a gap of 72 follows 31,397. Record-setting gaps are tracked as maximal gaps — gaps longer than every gap before them. As of 2026 the largest known maximal gap has length 1,854 and follows the prime 101,412,319,996,363,309,069, found by Robert Smith (Wikipedia, “Prime gap”; table of known maximal gaps, PrimePages).

The opposite question — how small gaps can stay — produced one of the great results of the twenty-first century. In 2013 Yitang Zhang proved that there are infinitely many pairs of primes no more than 70 million apart. Within months, a collaborative “Polymath” project and independent work by James Maynard drove the bound down; the established figure is now 246 (Wikipedia, “Prime gap”). Both proofs are built on sieve methods of the kind described in Volume 3.

2.9 Twin Primes

Primes two apart — 3 and 5, 5 and 7, 11 and 13, 17 and 19, 29 and 31, 41 and 43, 59 and 61, 71 and 73 below 100 — are twin primes. There are 8,169 twin pairs below a million and 808,675,888,577,436 below 10¹⁸ (OEIS A007508). The largest known pair, 2,996,863,034,895 × 2¹²⁹⁰⁰⁰⁰ ± 1, has 388,342 digits and was found in September 2016 by volunteers of the PrimeGrid and Twin Prime Search projects (Wikipedia, “Twin prime”).

Whether there are infinitely many twin primes is the twin prime conjecture, unproved. Zhang’s theorem is its weaker cousin: infinitely many pairs within 246 rather than within 2. What is known is that twin primes are rarer than primes by roughly an extra factor of ln x, a fact Viggo Brun proved in 1915–1919 with a new kind of sieve. Volume 3 tells that story, including the odd footnote that computing the constant Brun’s theorem leads to exposed a hardware bug in Intel’s Pentium processor.

2.10 Mersenne Primes and the Search for the Largest Known Prime

Euclid’s proof shows there is no largest prime, but there is always a largest known one, and for most of the last three centuries it has been a Mersenne prime: a prime of the form 2ⁿ − 1, named after the seventeenth-century friar Marin Mersenne, who corresponded with Fermat and catalogued them. 2² − 1 = 3, 2³ − 1 = 7, 2⁵ − 1 = 31 and 2⁷ − 1 = 127 are Mersenne primes; 2¹¹ − 1 = 2,047 = 23 × 89 is not. For 2ⁿ − 1 to be prime, n must itself be prime, but that is not enough.

Mersenne numbers are favoured because a special test, the Lucas–Lehmer test, decides whether 2ⁿ − 1 is prime far faster than any general method. Édouard Lucas devised it in the 1870s and D. H. Lehmer — the builder of the sieves in Volumes 6 and 7 — put it into its modern form around 1930. It was the Lucas–Lehmer test, run on the SWAC computer by Raphael Robinson in 1952, that produced the first Mersenne primes found by machine.

Since 1996 the hunt has been carried out by the Great Internet Mersenne Prime Search (GIMPS), founded by George Woltman, in which volunteers run the test on their own computers (mersenne.org). The largest known prime, as of October 2026, is the 52nd Mersenne prime found, 2¹³⁶²⁷⁹⁸⁴¹ − 1, which has 41,024,320 digits. It was discovered in October 2024 by Luke Durant using cloud-based graphics processors volunteered to GIMPS (Wikipedia, “Largest known prime number”).

The sieve has a supporting role here too. Before anyone runs a Lucas–Lehmer test on a candidate exponent, GIMPS first tries to find a small factor of 2ⁿ − 1, which would settle the matter cheaply. Any factor of 2ⁿ − 1 (with n prime) must have the form 2kn + 1 and must leave remainder 1 or 7 on division by 8, so the candidate factors are sieved by residues, exactly in the spirit of the Lehmers’ machines, before a single trial division is done.

2.11 A Picture of the Primes: The Ulam Spiral

In 1963, sitting through what he described as “a long and very boring paper” at a scientific meeting, the mathematician Stanisław Ulam began doodling: he wrote the numbers in a square spiral, 1 at the centre, and circled the primes. The primes did not scatter at random. They lined up along diagonals. Ulam and colleagues later plotted the spiral to about 100,000 on the MANIAC II computer at Los Alamos, and Martin Gardner put it on the cover of Scientific American in March 1964 (Wikipedia, “Ulam spiral”).

The diagonals are values of quadratic polynomials — in a square spiral, each diagonal line is a sequence like 4n² + bn + c — and some quadratics produce primes far more often than others. The classic example is Euler’s polynomial n² + n + 41, which is prime for every n from 0 to 39. The reason is, once again, the sieve: a polynomial whose values are never divisible by 2, 3, 5, 7, … except rarely passes the small-prime sieve far more often than a random number of the same size, so its values are disproportionately prime. Hardy and Littlewood made this precise in 1923 as their “Conjecture F,” which predicts the density of primes along each such line and remains unproved.

Exactly the same reasoning — which residues of a polynomial survive which moduli — powers the quadratic sieve that factored RSA-129 (Volume 10). The Ulam spiral is a picture of a sieve’s survivors.

2.12 What the Sieve Teaches

Three lessons from this volume carry forward through the series.

• Sieving beats testing. Listing primes by striding through a range and crossing out multiples costs a couple of operations per number. Testing each number separately costs far more. Every sieve machine in this series exists because of that asymmetry.
• The square root is the horizon. Only the primes up to √N are needed to sieve to N. That keeps sieves small, makes windows possible, and is why the Lehmers’ machines could use loops of modest length.
• Survivors have statistics. How many numbers survive a sieve, and how they are spaced, are questions about the primes themselves. Volume 3 turns those questions into a theory.

---

Next — Volume 3: Beyond Eratosthenes. How the basic sieve became a family: wheels that skip the multiples of 2, 3 and 5 before sieving begins, segmented sieves that list primes into the quintillions in a few kilobytes of memory, the sieves of Sundaram and Atkin, Legendre’s inclusion–exclusion, Brun’s sieve and the twin-prime constant, and the large and Selberg sieves — and the shift, crucial for the machines, from crossing out multiples to crossing out residue classes.