Home / Python / Example programs / Loops and numbers

Python program: All primes up to a limit (sieve)

List every prime number up to a limit with the Sieve of Eratosthenes.

The code

def primes_up_to(limit):
    is_prime = [True] * (limit + 1)
    is_prime[0] = is_prime[1] = False
    for n in range(2, int(limit ** 0.5) + 1):
        if is_prime[n]:
            for multiple in range(n * n, limit + 1, n):
                is_prime[multiple] = False
    return [n for n, p in enumerate(is_prime) if p]

print(primes_up_to(60))
print(len(primes_up_to(10_000)), "primes below 10,000")

Output

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59]
1229 primes below 10,000

How it works

Start by assuming every number is prime, then cross out the multiples of each prime. Whatever is left is prime. This is much faster than testing each number on its own.

Python features used

Learn the ideas behind it in the free lesson Loops.