About the Sieve of Eratosthenes - the oldest prime sieve
The Sieve of Eratosthenes finds all prime numbers up to a limit without a single division. You only count: cross out every second number after 2, every third after 3, and so on. What is left are the primes. More than two thousand years later, it is still one of the fastest ways to list them.
Eratosthenes of Cyrene
Eratosthenes lived from about 276 to 194 BC and was the head of the great library of Alexandria. He is best known for measuring the size of the Earth from the length of shadows in two cities. The sieve is named after him because Nicomachus of Gerasa described it as his method in the Introduction to Arithmetic, written around AD 100.
How the sieve works
Write down the numbers from 2 to N. The first number, 2, is prime: cross out 4, 6, 8 and every other multiple of 2. The next number that is left, 3, is prime: cross out 9, 12, 15 and so on. Keep going with 5, 7 and the next numbers that are left. A number that is never crossed out has no smaller factor, so it is prime.
Stop at the square root
Every composite number up to N has a prime factor that is no bigger than the square root of N. So once p² is more than N, there is nothing left to cross out. To find the primes up to 100 you only need 2, 3, 5 and 7, and for 1000 you need the primes up to 31.
How fast is it?
The sieve takes about N log log N steps, which grows only a little faster than N itself. Computers still use it, often in pieces called a segmented sieve, to list primes up to billions. To test whether one big number is prime, other methods are faster.
Frequently asked questions
Who invented the Sieve of Eratosthenes?
It is named after Eratosthenes of Cyrene, a Greek scholar of the third century BC. The oldest written description is by Nicomachus of Gerasa, around AD 100.
Why does the sieve start crossing out at p²?
Every smaller multiple of p has a smaller prime factor, so a smaller prime has already crossed it out.
How many primes are there below 1000?
There are 168 primes below 1000. The largest is 997.
Related tools
Sieve of Eratosthenes
Watch the Sieve of Eratosthenes find the prime numbers up to 100, 200, 500 or 1000. Each prime crosses out its multiples in its own colour, step by step.
Ulam spiral
Draw the Ulam spiral in your browser. Mark the primes, read the quadratic on each diagonal, and open Euler's unbroken run of 40 primes.
The Ulam spiral
How Stanisław Ulam's 1963 spiral lays the integers on a square grid, why primes gather on quadratic diagonals, and where Euler's forty primes sit when the spiral starts at 41.
The Collatz Conjecture
Explore the Collatz 3n+1 problem in your browser. Walk hailstone sequences, grow a geometric Collatz tree, and zoom the continuous Collatz fractal.
Ready to try it?
Open PictorX in your browser — no install, no credit card required to start.
Try the Sieve of Eratosthenes