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