generating primes

🏠

Primes are "non-composite" numbers, i.e they can only be divided by 1 and by themselves. The rule for primes also states that 0 and 1 are not prime.

Write a program that efficiently generates all primes up to n.

Solution

You might, initially think of implementing a brute-force "trial division":

 1def generate_primes(n):
 2    primes = []
 3    for i in range(2, n):
 4        for j in range(i-1, 1, -1):
 5            if i % j == 0:
 6                break
 7        else:
 8            primes.append(i)
 9    return primes
10
11print(generate_primes(100))

That's fine, however it's horribly inefficient for large prime numbers.

The Sieve of Eratosthenes

A better solution is an ancient algorithm: the prime sieve of Eratosthenes. It's fascinating because once again, you have to flip your thinking to discover it. Instead of attempting to compute primes, it eliminates non-primes.

1def generate_primes(n):
2    primes = [False, False] + [True] * (n-2)
3    for i in range(2, n//2):
4        for j in range(i*2, n*primes[i], i):
5            primes[j] = False
6    return [i for i in range(n) if primes[i]]