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]]