← All writing Ancient algorithms, 12 min read

The sieve of Eratosthenes, from Nicomachus to a segmented sieve in Python

The sieve of Eratosthenes as Nicomachus gives it in Introduction to Arithmetic I.13, then the standard, segmented and wheel sieves in Python, tested and timed.

Write out the numbers from 2 to 100. Cross out the multiples of 2 after 2, then of 3, 5 and 7, and the 25 numbers left standing are the primes below 100. That is the sieve of Eratosthenes, named after Eratosthenes of Cyrene (c. 276 to 194 BCE). The earliest surviving description is by Nicomachus of Gerasa, about 300 years later.

I read Nicomachus’s text in M. L. D’Ooge’s 1926 English translation and in Hoche’s 1866 Greek edition, coded his version as written, and then built the 3 versions used today: the standard sieve, a segmented sieve and a wheel sieve. All 4 are checked against trial division and timed up to 1,000,000 (sieve.py on GitHub). The series is Ancient algorithms, implemented.

The problem

A prime is a whole number greater than 1 whose only divisors are 1 and itself. The direct way to list primes is trial division: for each number, divide by the primes in turn, and stop at the first one that divides it or at the first one above its square root. A prime needs a division by every prime up to its square root.

The sieve works from the other side. It takes each prime and marks everything it divides. Marking the multiples of 3 means stepping through the list 3 places at a time. There is no division at all.

Who wrote it, and when

  • Eratosthenes of Cyrene, c. 276 to 194 BCE, librarian at Alexandria. The 1926 English edition of Nicomachus gives his dates as c. 275 to 194 BCE in 1 note and c. 276 to 194 BCE in another. No work of his on the sieve survives.
  • Nicomachus of Gerasa, Introduction to Arithmetic, Book I, chapter 13. His dates are uncertain. Robbins, in D’Ooge, Robbins and Karpinski (1926, p. 72), concludes only that his life fell between the middle of the 1st and the middle of the 2nd century CE; c. 100 CE is a round figure inside that range. Robbins takes his Gerasa to be the city of the Decapolis, modern Jerash in Jordan.
  • The editions. The Greek is R. Hoche’s Teubner edition (Leipzig, 1866), p. 29. The English is M. L. D’Ooge’s translation, pp. 204 to 205 of D’Ooge, Robbins and Karpinski (Macmillan, 1926). D’Ooge died in 1915 with the translation finished. F. E. Robbins revised it and prepared the rest of the volume, apart from the chapters L. C. Karpinski wrote (preface, 1925). The book was published in the United States in 1926, so it is in the public domain there, and I quote the translation in full below.

The source text

The sentence that names Eratosthenes, from Hoche’s edition:1

Ἡ δὲ τούτων γένεσις ὑπὸ Ἐρατοσθένους καλεῖται κόσκινον

My translation: “The production of these is called by Eratosthenes the sieve.” Koskinon (κόσκινον) is the ordinary Greek word for a sieve. D’Ooge’s translation of I.13.2 to 13.6:

The production of these numbers is called by Eratosthenes the ‘sieve,’ because we take the odd numbers mingled together and indiscriminate and out of them by this method of production separate, as by a kind of instrument or sieve, the prime and incomposite by themselves, and the secondary and composite by themselves, and find the mixed class by themselves.

The method of the ‘sieve’ is as follows. I set forth all the odd numbers in order, beginning with 3, in as long a series as possible, and then starting with the first I observe what ones it can measure, and I find that it can measure the terms two places apart, as far as we care to proceed. And I find that it measures not as it chances and at random, but that it will measure the first one, that is, the one two places removed, by the quantity of the one that stands first in the series, that is, by its own quantity, for it measures it 3 times; and the one two places from this by the quantity of the second in order, for this it will measure 5 times; and again the one two places further on by the quantity of the third in order, or 7 times, and the one two places still farther on by the quantity of the fourth in order, or 9 times, and so ad infinitum in the same way.

Then taking a fresh start I come to the second number and observe what it can measure, and find that it measures all the terms four places apart, the first by the quantity of the first in order, or 3 times; the second by that of the second, or 5 times; the third by that of the third, or 7 times; and in this order ad infinitum.

Again, as before, the third term 7, taking over the measuring function, will measure terms six places apart, and the first by the quantity of 3, the first of the series, the second by that of 5, for this is the second number, and the third by that of 7, for this has the third position in the series.

And analogously throughout, this process will go on without interruption, so that the numbers will succeed to the measuring function in accordance with their fixed position in the series; the interval separating terms measured is determined by the orderly progress of the even numbers from 2 to infinity, or by the doubling of the position in the series occupied by the measuring term, and the number of times a term is measured is fixed by the orderly advance of the odd numbers in series from 3.

M. L. D’Ooge, revised by F. E. Robbins, in Nicomachus of Gerasa: Introduction to Arithmetic (1926), pp. 204 to 205

“Two places apart” means 2 terms are skipped. In the series 3, 5, 7, 9, 11, 13, 15, the number 3 marks 9 and then 15, with 5 and 7, then 11 and 13, in between.

Nicomachus then says to mark the numbers with signs. The ones never measured “are primes and incomposites, sifted out as it were by a sieve”; the rest are composite.

What the text leaves open

  1. Only odd numbers. In Nicomachus the primes are a class of odd numbers (I.11; Robbins’s note on p. 201 points out that Euclid’s definition admits 2). His series starts at 3, so his sieve gives the odd primes.
  2. Which numbers do the measuring. The text says the numbers succeed to the measuring function “in accordance with their fixed position in the series”, which reads as every odd number, composites like 9 and 15 included. Robbins’s note on this passage says the text seems to imply that, and that only the primes are needed. My koskinon function follows the text literally; it is slower and gives the same primes.
  3. Where each number starts. Nicomachus has 5 start at 15 and 7 at 21, 3 times themselves. The modern sieve starts each prime at its square, 25 and 49, because the smaller multiples were already crossed out by smaller primes.
  4. When to stop. “As far as we care to proceed.” The text gives no rule for stopping. The modern rule is to stop once the prime’s square passes the limit.
  5. Eratosthenes’s own version. Nothing of it survives, so whether he sieved odd numbers only, or all numbers, is not known.

How the sieve of Eratosthenes works: 1 to 100

The standard version on 2 to 100:

  1. Write out 2 to 100. The first number, 2, is prime. Cross out 4, 6, 8, …, 100: 49 crossings.
  2. The next number standing is 3. Cross out from 9, its square, every 3rd number: 9, 12, …, 99. That is 31 crossings, some of them on numbers already crossed.
  3. The next is 5. Cross out 25, 30, …, 100: 16 crossings.
  4. The next is 7. Cross out 49, 56, …, 98: 8 crossings.
  5. The next is 11, and 11 × 11 = 121 is past 100, so stop. Everything left is prime.

That is 104 crossings. They remove the 74 composite numbers from 4 to 100, and 25 primes remain:

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

Starting each prime at twice itself, the more obvious choice, makes 113 crossings. Nicomachus’s version on the odd numbers 3 to 99 makes 56 marks, read literally so that 9, 15, 21 and the other odd composites also take a turn. It never touches the even numbers. Those counts come from crossing_count and mark_count in the repo.

Why the sieve works

Every composite number n can be written as a × b with a no larger than b. Then a × a ≤ n, so a is at most the square root of n, and the smallest prime factor of a is too. So every composite up to a limit N has a prime factor no larger than the square root of N, and crossing out the multiples of those primes catches all of them.

That gives both modern shortcuts:

  • Stop at the square root. After the primes up to sqrt(N) are done, nothing composite is left.
  • Start at the square. A multiple k × p with k < p has a prime factor smaller than p, so it was crossed out already. The first new multiple of p is p × p.

Nicomachus’s version also works without either shortcut: every odd composite a × b with both factors odd and at least 3 is reached when a takes its turn as the measure, since a measures every odd multiple of itself from 3 × a on.

The Python

The standard sieve, with a bytearray of 1 byte per number:

from math import isqrt


def sieve_of_eratosthenes(limit: int) -> list[int]:
    """Primes up to limit: cross out from p*p for each prime p."""
    is_prime = bytearray([1]) * (limit + 1)
    is_prime[: min(2, limit + 1)] = bytes(min(2, limit + 1))  # 0 and 1
    for p in range(2, isqrt(limit) + 1):
        if is_prime[p]:
            is_prime[p * p :: p] = bytes(len(range(p * p, limit + 1, p)))
    return [n for n in range(limit + 1) if is_prime[n]]


print(sieve_of_eratosthenes(100))  # the 25 primes above

The slice assignment is_prime[p * p :: p] = ... crosses out every p-th entry in 1 step, inside CPython’s C code.

Nicomachus’s version, as he describes it, records which numbers measure each odd number:

def koskinon(limit: int) -> dict[int, list[int]]:
    """Each odd number from 3 to limit, with the numbers that measure it."""
    marks = {n: [] for n in range(3, limit + 1, 2)}
    for measure in marks:  # every term takes its turn, composites too
        for n in range(3 * measure, limit + 1, 2 * measure):
            marks[n].append(measure)
    return marks


print(koskinon(45)[45])  # [3, 5, 9, 15]
print([n for n, m in koskinon(50).items() if not m])  # the odd primes to 50

Stepping 2 * measure through the numbers is stepping measure places through the odd series, which skips measure - 1 terms. For the term in position k, the value is 2k + 1, so it skips 2k terms: Nicomachus’s “doubling of the position in the series”.

The repo version adds the segmented and wheel sieves, trial division, and input checks. The tests check:

  • Nicomachus’s examples: 3 marks 9, 15, 21, 27 and measures them 3, 5, 7, 9 times; 5 marks 15, 25, 35; 7 marks 21, 35, 49;
  • that the term in position k skips 2k terms, for k up to 40;
  • his 9 and 25, composite and prime to one another;
  • the 25 primes to 100 and the 104, 113 and 56 counts;
  • all 4 sieves against trial division for random limits up to 2,000 and segment sizes up to 200, with Hypothesis;
  • the 9,592 primes below 100,000, from all 4 sieves. The benchmark checks the 78,498 primes below 1,000,000.

The segmented sieve and the wheel

The standard sieve needs 1 byte per number: 1 MB for a limit of 1,000,000 and 1 GB for 1,000,000,000.

A segmented sieve keeps memory small. It sieves the primes up to sqrt(N) first, the base primes. Then it walks through 2 to N in blocks, and in each block crosses out the multiples of the base primes, starting from the first multiple inside the block. For 1,000,000 the base primes are the 168 primes below 1,000, and each block is 32,768 bytes. Because each block only needs the base primes, a segmented sieve can start its first block anywhere, for example at 1012, without touching the numbers below it. The repo version always starts at 2.

A wheel sieve stores fewer numbers. Every prime above 5 leaves remainder 1, 7, 11, 13, 17, 19, 23 or 29 when divided by 30, since any other remainder shares a factor 2, 3 or 5 with 30. So the wheel keeps 8 of every 30 numbers, 27% of the memory, and never visits multiples of 2, 3 or 5. For 1,000,000 that is 266,672 bytes.

Timings in pure Python 3.13 on an Apple M1 Pro, best of 3 runs:

Method10,000100,0001,000,000
Trial division3.6 ms55.3 ms1,007 ms
Nicomachus, literal2.0 ms29.0 ms805 ms
Standard sieve0.3 ms3.3 ms33.1 ms
Segmented sieve0.3 ms3.2 ms32.1 ms
Wheel sieve, mod 300.7 ms8.1 ms93.7 ms

The wheel sieve does the least work and takes about 2.8 times as long here, because its inner loop is Python code and the standard sieve’s inner loop is 1 slice assignment that runs in C. It uses 27% of the memory. The segmented sieve runs as fast as the standard one, and its working array is 3% of the standard sieve’s at 1,000,000. The script is benchmarks/sieve_compare.py in the repo; the 1,000,000 column for trial division and Nicomachus needs --full.

Parallels and lineage

  • Euclid, Elements VII. Nicomachus’s word for “divides” is Euclid’s “measures”, and his “prime to one another”, for 9 and 25, is Euclid’s Book VII, definition 12. The Euclidean algorithm post covers Book VII, propositions 1 and 2.
  • Trial division tests 1 number at a time and is the reference the tests compare against. The sieve lists every prime in a range at once.

What is debated

  • Whether Eratosthenes devised the method. The attribution rests on 1 sentence in Nicomachus, about 300 years later. Robbins, in D’Ooge, Robbins and Karpinski (1926, p. 36), writes that it is not certain that even for the sieve Nicomachus went to Eratosthenes himself.
  • What Nicomachus meant by the measuring terms. The text reads as all odd numbers, composites included. Robbins’s note on I.13 says the usual account has only the odd primes measuring, and that Nicomachus may not have meant to be read so strictly. Heath’s account is the one he cites: “if n be a prime number, its multiples appearing in the series are found by passing over n-1 terms at a time” (1921, vol. 1, p. 100).
  • The date of Nicomachus. Between the middle of the 1st and the middle of the 2nd century CE, on Robbins’s reading of the evidence; c. 100 CE is a round figure.

Key takeaways

  • The sieve of Eratosthenes lists all primes up to a limit by crossing out multiples, with no division.
  • No text of Eratosthenes on it survives. Nicomachus of Gerasa, c. 100 CE, describes it in Introduction to Arithmetic I.13 and credits Eratosthenes with the name koskinon, “sieve”.
  • Nicomachus sieves only odd numbers and lets every odd number measure. The modern version uses only primes, starts at p * p and stops at the square root of the limit.
  • 1 to 100 leaves 25 primes after 104 crossings.
  • The segmented sieve runs at the standard sieve’s speed with a working array of 32,768 bytes. In pure Python the wheel takes about 2.8 times as long as the standard sieve, because the standard sieve’s inner loop is 1 slice assignment in C.

Sources

  • Nicomachus of Gerasa, Introduction to Arithmetic, ed. R. Hoche, Teubner, 1866, I.13.2, p. 29.
  • M. L. D’Ooge, F. E. Robbins and L. C. Karpinski, Nicomachus of Gerasa: Introduction to Arithmetic, Macmillan, 1926. Translation (D’Ooge) of I.13 on pp. 203 to 205, with Robbins’s notes; primes as odd numbers, p. 201 note; Nicomachus’s date, p. 72; Eratosthenes as a source, pp. 35 to 36.
  • T. L. Heath, A History of Greek Mathematics, vol. 1, Oxford, 1921, p. 100.

Footnotes

  1. The scan of Hoche’s edition I used is machine-read text with the accents garbled. The letters are clear; I restored the accents and breathings by the standard spelling of each word. ↩

Common questions

What is the sieve of Eratosthenes?↓

A method for listing every prime up to a limit. Write the numbers out, then for each prime in turn cross out its multiples. The numbers never crossed out are the primes. It needs no division.

Who discovered the sieve of Eratosthenes?↓

It is credited to Eratosthenes of Cyrene (c. 276 to 194 BCE), but no work of his on it survives. The attribution comes from Nicomachus of Gerasa, Introduction to Arithmetic I.13, written about 300 years later, c. 100 CE, who says the method 'is called by Eratosthenes the sieve'. F. E. Robbins, in the 1926 English edition, notes it is not certain Nicomachus took it from Eratosthenes directly.

What is the sieve of Eratosthenes for 1 to 100?↓

It leaves 25 primes: 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. You only need to sieve with 2, 3, 5 and 7, because 11 × 11 = 121 is past 100. Starting each prime at its square, that is 104 crossings, which remove the 74 composite numbers from 4 to 100; some numbers are crossed more than once.

What is the main idea behind the sieve?↓

A composite number has a prime factor no larger than its square root. So once you have crossed out the multiples of every prime up to the square root of the limit, whatever is left is prime. The sieve finds primes by removing composites, instead of testing each number.

What is a segmented sieve?↓

A sieve that works on 1 block of numbers at a time. It first sieves the primes up to the square root of the limit, then uses them to cross out multiples in each block. Its working array is 1 block, plus the list of base primes.

Share this
← More writing Get in touch