Math: sieve of Eratosthenes

A prime is a whole number greater than 1 whose only divisors are 1 and itself: 2, 3, 5, 7, 11, .... Testing each number for primality one by one is slow. The sieve of Eratosthenes is a classic, much faster idea from ancient Greece.

Start by assuming every number from 2 to n is prime. Then walk upward: the first number still marked prime is 2, so cross out all of its multiples (4, 6, 8, ...) — they can't be prime. Move to the next surviving number (3), cross out its multiples, and so on. Whatever is left standing is prime.

In plain steps (you write the Python):

mark every number 0..n as "prime" to begin with
knock out 0 and 1 — they aren't prime
for each p from 2 up to sqrt(n):
    if p is still marked prime:
        cross out p*p, p*p+p, p*p+2p, ...  (every multiple of p, up to n)
collect every index still marked prime

(You only need to start crossing out at p * p, since smaller multiples were already handled by smaller primes.)

Your task

Write primes_up_to(n) returning a list of every prime <= n, in ascending order.

primes_up_to(10)  # [2, 3, 5, 7]
primes_up_to(1)   # []
primes_up_to(2)   # [2]
primes_up_to(20)  # [2, 3, 5, 7, 11, 13, 17, 19]

Hint: build the boolean sieve, then collect every index i whose entry is still True.