Finding every prime
A prime number is a whole number greater than 1 that can be divided evenly only by 1 and by itself. 2, 3, 5 and 7 are prime. 6 is not, because 2 × 3 = 6.
Suppose you want every prime up to 100. The direct way is to test each number: try dividing it by every smaller number and see whether anything divides evenly. That works, and it is a lot of divisions.
More than two thousand years ago, the Greek scholar Eratosthenes found a way that needs no division at all. Do not test numbers to see if they are prime. Go the other way: cross out everything that is not.
The method
Write out all the numbers from 2 up to your limit
Every one of them is a candidate.
Take the first number not crossed out. It is prime
At the start that is 2.
Cross out all its multiples
4, 6, 8, 10 and so on. They have 2 as a divisor, so they cannot be prime.
Move to the next number still standing, and repeat
That is 3: cross out 6, 9, 12. Then 5. Then 7.
Whatever is left at the end is prime
It was never a multiple of anything smaller.
Start. Write down every number from 1 to 100. 1 is not counted as a prime, so cross it out. Then start at 2.
- Still standing
- 99
- Crossed out
- 1
It is called a sieve because the numbers that are not prime fall through, and the primes are what stays behind.
Why the next one standing is always prime
When the method reaches a number that has not been crossed out, it declares it prime without checking anything. Why is that safe?
If the number had a smaller divisor, it would have a smaller prime divisor. And the multiples of every smaller prime have already been crossed out. So it would be gone. It is still standing, so no smaller prime divides it. It is prime.
Each prime has its own rhythm
Watch how the crossing-out moves. For 2 it hits every second number. For 3, every third. For 5, every fifth. Each prime sweeps along the row at its own steady pace, like a drummer with a different tempo.
Lay the beats over each other and they cover most of the row. The primes are the places where no beat lands.
No formula predicts where those gaps fall. They follow from the overlapping rhythms, and that is why primes look so irregular: 2, 3, 5, 7, 11, 13, then a jump to 17, 19, 23, another to 29.
Two shortcuts
Start crossing out at the prime's square. When you get to 5, the numbers 10, 15 and 20 are already gone: they were removed as multiples of 2 or 3. The first multiple of 5 that nobody has touched is 5 × 5 = 25.
Stop when the prime's square passes the limit. For numbers up to 100, you only need to sieve with 2, 3, 5 and 7. The next prime is 11, and 11 × 11 = 121 is beyond 100, so it has nothing new to cross out.
Example
Four passes for a hundred numbers
Up to 100, the sieve runs with just four primes: 2, 3, 5 and 7. After those four passes, the 25 numbers left standing are all the primes below 100.
To find every prime below 1,000,000, you only sieve with the primes below 1,000.
def primes_up_to(limit):
is_prime = [True] * (limit + 1)
is_prime[0] = is_prime[1] = False
number = 2
while number * number <= limit:
if is_prime[number]:
for multiple in range(number * number, limit + 1, number):
is_prime[multiple] = False
number += 1
return [n for n in range(limit + 1) if is_prime[n]]
primes_up_to(30) # [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]How fast it is
Crossing out is very cheap: a jump and a mark. The multiples of 2 are half the numbers, the multiples of 3 a third, the multiples of 5 a fifth. Added up over all the primes, the total number of marks is only a little more than the size of the list.
That makes the sieve the standard way to find all primes up to a limit. Its cost is memory: one mark per number. It is the wrong tool for testing a single enormous number, which has its own methods.
| Task | Good approach |
|---|---|
| All primes up to a few million | The sieve |
| Is this one small number prime? | Try dividing by numbers up to its square root |
| Is this one huge number prime? | Specialised tests, used in cryptography |
Key takeaways
- The sieve finds all primes up to a limit by crossing out multiples, with no division.
- The first number not yet crossed out is always prime.
- Each prime removes its multiples at its own regular spacing. The primes are what no spacing hits.
- Start crossing out at the prime's square, and stop once that square passes the limit.
- It is fast and simple, and needs memory for every number up to the limit.