Checking whether a single number is prime is easy, but what if you need every prime number up to some limit? Checking each number one by one works, but it's slow for large ranges. The Sieve of Eratosthenes is a 2,000-year-old algorithm that solves this much faster by eliminating multiples instead of testing each number individually.
The idea: start by assuming every number is prime, then walk through the list using a loop and cross off every multiple of each prime you find, starting from its square.
Python Program to Print Prime Numbers Using the Sieve of Eratosthenes
def sieve_of_eratosthenes(n):
is_prime = [True] * (n + 1)
is_prime[0] = is_prime[1] = False
for i in range(2, int(n ** 0.5) + 1):
if is_prime[i]:
for multiple in range(i * i, n + 1, i):
is_prime[multiple] = False
return [num for num, prime in enumerate(is_prime) if prime]
limit = 50
primes = sieve_of_eratosthenes(limit)
print(f"Prime numbers up to {limit}:")
print(primes)Output:
Prime numbers up to 50:
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]
Two details make this efficient: the outer loop only needs to go up to sqrt(n), because any composite number below n has at least one factor at or below its square root. And when marking multiples, it starts at i * i rather than 2 * i, since any smaller multiple of i would already have been crossed off by a smaller prime.
Testing each number up to n individually for primality costs roughly O(n √n). The sieve does the same job in O(n log log n), which is close to linear — a huge difference once n gets into the millions, which is exactly why this is the standard approach used in competitive programming and interview questions that ask for "all primes up to N."