How an ancient Greek algorithm still efficiently hunts for prime numbers today
In short: Long before modern computers, Eratosthenes of Cyrene devised a simple, elegant method to isolate prime numbers. By iteratively marking multiples of each discovered prime as composite, this ancient algorithm avoids the tedious division required by other methods. It remains a foundational, highly efficient tool for number theory and computational mathematics.
The sieve of Eratosthenes is a classic algorithm for identifying all prime numbers up to a specified limit. Unlike trial division, which tests each candidate number for divisibility by every preceding prime, the sieve works by systematically eliminating composite numbers. Starting with the number 2, the algorithm marks all its multiples as non-prime. It then moves to the next unmarked number, which is guaranteed to be prime, and repeats the process for its multiples. This continues until all numbers up to the chosen limit have been processed, leaving only the primes remaining.
Attributed to the 3rd-century BCE mathematician Eratosthenes of Cyrene, the earliest known description appears in Nicomachus of Gerasa's 2nd-century CE work, Introduction to Arithmetic. While the original method may have focused on odd numbers, the core logic remains unchanged: it relies purely on addition rather than multiplication or division. Modern refinements, such as starting the marking process at the square of the prime or using wheel factorization to skip even numbers, significantly optimize the speed of the calculation.
Despite its efficiency, the sieve faces practical challenges in modern computing. As noted by Sorenson, the primary issue is memory usage and cache performance. Because the algorithm traverses a large array of numbers, it exhibits poor locality of reference, which can slow down execution on large datasets. To address this, segmented sieves were developed in the 1970s. These divide the range into smaller, manageable segments, allowing the algorithm to process portions of the data at a time, thereby optimizing memory usage while maintaining the mathematical elegance of the original approach.
The sieve is not merely a historical curiosity; it is a powerful tool for finding primes in arithmetic progressions. Its time complexity is O(n log log n), making it one of the most effective ways to generate smaller primes. By transforming a complex division problem into a series of simple additions, Eratosthenes provided a blueprint for computation that remains relevant over two millennia later.
Opens the Intellect+ feed with this card first. Swipe up for the next one.
Sources
- Summary by Intellect · source: Sieve of Eratosthenes
To cite this card, link to https://intellectplus.co.uk/app/science-sieve-of-eratosthenes.
How we source, check and correct cards: Editorial standards.
General information, not professional advice. Spotted an error? Flag the card or see corrections and complaints.
Intellect Plus is a visual educational discovery platform for exploring fascinating facts and ideas. Brain Food, Not Brain Rot. What is Intellect Plus?
Related
More in Number theory · More in Science · Latest · A–Z · All topics