The sieve of Eratosthenes: revisited

Gerard McNally

24 January 2019

• Click to share on X (Opens in new window)
• Click to share on Facebook (Opens in new window)
• Click to share on Reddit (Opens in new window)
• Click to share on LinkedIn (Opens in new window)
• Click to share on Threads (Opens in new window)
• Click to share on Mastodon (Opens in new window)

Here are some definitions (with which many readers will, no doubt, already be familiar) that are pertinent to the discussion that lies ahead.

• A prime number is commonly defined as “a positive integer with exactly two distinct factors: unity and the prime number itself”.
• If a number is not prime, it is termed composite.
• The first positive integer, 1, is considered neither prime nor composite.

Greek mathematician Eratosthenes is also credited with being the first person to estimate the Earth’s circumference. Image: Wikimedia commons.

An algorithmic approach to identifying all primes less than a given number has been known since ancient times. Attributed to Eratosthenes, who lived in 3rd century BCE Greece, it works as follows.

• Disregarding 1, list all the positive integers up to the required number
• The lowest remaining number is, by definition, prime
• Strike off all the remaining multiples of the newly identified prime which, by definition, are composite
• Continue the process iteratively

This algorithm, characterised by separating the primes from the “unwanted” composites, is widely known as the sieve of Eratosthenes.

To illustrate, here are the first four iterations for the numbers up to 50 inclusive. (The status of numbers shown in black type is not yet determined; numbers in blue are confirmed composite; those in red type are confirmed prime.)

1st iteration: (1) 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

2nd iteration: (1) 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

3rd iteration: (1) 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

An initial observation might be that each iteration produces only one new confirmed prime. However, a quick check of the third iteration shows that all unconfirmed numbers in black type are, in fact, prime. This observations, of course, rely on our being able to recognise primes by inspection or to perform some other test, independent of the sieve algorithm (which will, of course, upon further iterations, confirm our findings).

Into the classroom

As a schoolteacher, I want my learners to be able to execute the algorithm to identify primes; but I don’t want this done blindly. I want them to discover the interplay between primes and composites, and the richness of understanding of the positive integers that this reveals. The sieve algorithm is often carried out on a grid, resulting in something like this (with 1 omitted and after the multiples have been struck out).

However, my earlier representation of the individual iterations helps, I feel, to slow down the process allowing pupils to notice how it unfolds and to spot any emerging patterns. A conspicuous feature I would like to draw attention to at this stage is the level of duplication in striking out composites. The grid above also contains a dot for each “strike” (which, of course, provides a factor count for each composite).

Consider, now, the list form of second iteration. A pattern emerges in the distribution of confirmed composites. (Recall that, by the sieve algorithm, numbers in black type may or may not be composite-–or prime-–but numbers in blue have been verified composite). The sequence is represented again below, this time using C to denote composites, P for primes and ? to denote numbers of unconfirmed status; the colour convention used above is retained.

(1) P P C ? C ? C C C ? C ? C C C ? C ? C C C ? C ? C C C ? C

Notice that, from the sixth term onwards, the composites alternate in groups of three and one. It is not difficult, based on the workings of the algorithm, to become convinced that this pattern will persist indefinitely. This implies that primes can only lie immediately before or after a multiple of 6, a result that is not at first obvious but is easy to understand, and prove, once discovered. Given the difficulty in deciding whether a large number is prime or not, a quick division by 6 can rule out as composite any number whose remainder is not either 1 or 5.

Re-interpreting the sieve

Eratosthenes’ sieve is clearly based on the kind of definition of a prime given above, with its focus only on factors. But this definition does not do full justice to the importance of primes which, as their name suggests, are the first numbers: the numbers from which all other numbers can be constructed using multiplication. A commonly used analogy is with the chemical elements, from which all substances are built; this likens the primes to distinct atoms (or the monatomic gases) while the composites correspond to compounds from simple ones like water or salt to the biochemical macromolecules.

Let us redefine the primes, then, in this manner:
Those positive integers greater than unity which are not themselves the product of two or more smaller numbers but from which, collectively, all composite numbers arise as products.

This definition suggests an alternative algorithm.

• • Disregarding 1, list all the positive integers up to the required number
  • The lowest remaining number is, by definition, prime
  • Identify and explicate any numbers on the list that can be constructed by multiplying confirmed primes together – these are, by definition, composite
  • The smallest number not verified as composite must be the next prime
  • Multiply every number whose status has been verified – prime or composite – by the new prime
  • Continue the process iteratively

Here are the first three iterations of this algorithm for the numbers 1 – 50, in tabular form.

In the first iteration, above, the first prime (shown red) and four composites (not necessarily the first four – shown in blue) have been confirmed; all remaining numbers (black) are of undetermined status.

Iteration 2 has two confirmed primes, giving rise to a total of twelve composites within the range under consideration.

The third prime and eight more composites appear in iteration 3.

The advantages of the revised algorithm

Both the original and revised algorithms make clear what the next prime is, while the status of all other numbers in black await determination. Importantly for my purposes the new algorithm, unlike the sieve, at the point of identifying composites also generates an explicit prime factorisation for each. Note that this would not be the case if, at the fifth step, it allowed for multiplying all numbers by each newly confirmed prime: a worthwhile trade-off, I feel, for the loss of efficiency in relation to the bulk identification of composites the sieve provides (recall that all composites – and, consequently, primes – up to 50 had been identified by the fourth iteration of the sieve). The process of prime factorisation, somewhat paradoxically, emerges as a constructive rather than a destructive one. I want my learners to be able ultimately to determine whether a given number is prime and, if not, to decompose it into its prime factors. However, I feel a deeper understanding of these processes is added by this complementary approach. For me, it provides a beautiful illustration (although not, of course, a proof) of the fundamental theorem of arithmetic which tells us that every positive whole number can be expressed as a unique product of primes. This, in turn, provides us with the reason why 1 is not considered prime: introduce 1 into any prime factorisation and the uniqueness is gone. It also affords opportunities for students to generate their own questions and conjectures – for example:

• What is the first composite that will be determined by the next iteration?
• What does this tell us about the numbers before the next composite whose status (prime or composite) is not yet determined?
• How many iterations are needed to be sure of finding all the primes below a given number?

To conclude the discussion, I believe that by combining a slowed-down application of the sieve of Eratosthenes in conjunction with the revised algorithm offered above we can open doors to an abundance of mathematical ideas, including those underlying some of the greatest works in the history of the discipline such as Euclid’s proof of the infinitude of primes, the prime number theorem and the Riemann Hypothesis, to name but a few.

Gerard McNally

Gerry became a secondary school maths teacher in Scotland after a career change 12 years ago; he is currently working for Glasgow City Council. His ultimate ambition is for all of his learners to see their mathematics education as a gift rather than a duty.

germinalmaths.com    All articles by Gerard