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.

is_prime = [True] * (n + 1)
is_prime[0] = is_prime[1] = False
for p in range(2, int(n ** 0.5) + 1):
    if is_prime[p]:
        for multiple in range(p * p, n + 1, p):
            is_prime[multiple] = False

(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.