Sieve of Eratosthenes

Start with a list of True values. For each prime p, cross out (set to False) every multiple of p. You can start crossing out at p * p.

def primes_up_to(n):
    if n < 2:
        return []
    is_prime = [True] * (n + 1)
    is_prime[0] = is_prime[1] = False
    p = 2
    while p * p <= n:
        if is_prime[p]:
            for m in range(p * p, n + 1, p):
                is_prime[m] = False
        p += 1
    return [i for i, ok in enumerate(is_prime) if ok]

Any smaller multiple of p, such as 3p, was already crossed out by a smaller prime, so crossing out starts at p * p, and the outer loop can stop once p * p > n. The sieve runs in O(n log log n) time, which is close to linear.