DSA The Sieve of Eratosthenes

The sieve of Eratosthenes is a method that finds every prime up to a limit by crossing out multiples. A prime is a whole number above 1 with no divisor besides 1 and itself.

Cross out the multiples of 2

Every even number above 2 leaves the table. The odd numbers and 2 itself stay standing.

limit = 20
standing = [True] * (limit + 1)
standing[0] = False
standing[1] = False
for m in range(4, limit + 1, 2):
    standing[m] = False
print("standing after crossing 2:", [n for n in range(limit + 1) if standing[n]])

Then cross out the multiples of 3

The next prime standing is 3, so its multiples fall next. Numbers crossed earlier stay crossed.

limit = 30
standing = [True] * (limit + 1)
standing[0] = False
standing[1] = False
for p in [2, 3]:
    for m in range(p * p, limit + 1, p):
        standing[m] = False
print("standing after 2 and 3:", [n for n in range(limit + 1) if standing[n]])

Count the crossings on a small sieve

A counter rises only when a standing number falls. Repeated crossings of one number are not counted twice.

def sieve(limit):
    standing = [True] * (limit + 1)
    standing[0] = False
    standing[1] = False
    crossings = 0
    p = 2
    while p * p <= limit:
        if standing[p]:
            for m in range(p * p, limit + 1, p):
                if standing[m]:
                    standing[m] = False
                    crossings += 1
        p += 1
    return [n for n in range(limit + 1) if standing[n]], crossings

primes, crossings = sieve(30)
print("primes to 30:", primes)
print("crossings:", crossings)

Example

limit = 100
standing = [True] * (limit + 1)
standing[0] = False
standing[1] = False
crossings = 0
snapshots = {}
p = 2
while p * p <= limit:
    if standing[p]:
        for m in range(p * p, limit + 1, p):
            if standing[m]:
                standing[m] = False
                crossings += 1
    if p in (2, 3):
        snapshots[p] = [n for n in range(limit + 1) if standing[n]]
    p += 1
print("standing after crossing 2:", snapshots[2])
print("standing after crossing 3:", snapshots[3])
primes = [n for n in range(limit + 1) if standing[n]]
print("primes to 100:", primes)
print("prime count:", len(primes))
print("crossings:", crossings)

Key points

The sieve of Eratosthenes finds every prime up to a limit by crossing out multiples.
A prime is a whole number above 1 with no divisor besides 1 and itself.
Crossing out starts at the prime squared, since smaller multiples fell earlier.
A number still standing after its turn was never crossed out.
Every composite number is crossed out when its smallest prime factor runs.
The crossing count measures the work the sieve performs.

In this example, the table starts with every number standing. The first snapshot shows the damage done by crossing multiples of 2. The second snapshot shows the table after multiples of 3 also fall. Later primes cross out the few composites still standing. The final list holds the 25 primes up to 100.

Try it Yourself

Edit the code, then press Run.

Running is simulated · Python Playground

limit = 100
standing = [True] * (limit + 1)
standing[0] = False
standing[1] = False
crossings = 0
snapshots = {}
p = 2
while p * p <= limit:
    if standing[p]:
        for m in range(p * p, limit + 1, p):
            if standing[m]:
                standing[m] = False
                crossings += 1
    if p in (2, 3):
        snapshots[p] = [n for n in range(limit + 1) if standing[n]]
    p += 1
print("standing after crossing 2:", snapshots[2])
print("standing after crossing 3:", snapshots[3])
primes = [n for n in range(limit + 1) if standing[n]]
print("primes to 100:", primes)
print("prime count:", len(primes))
print("crossings:", crossings)

Exercise

During a sieve to 50, which number crosses out 49?

5 7 11 49 itself