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.