Решето Эратосфена

Решето Эратосфена находит все простые числа до n. Алгоритм отмечает все кратные каждого найденного простого как составные; оставшиеся неотмеченными числа и есть простые.

Сложность: время O(n log log n) — почти линейное; память: O(n) под массив флагов. Один из самых эффективных способов получить таблицу простых.

def sieve(n):
    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 k in range(p * p, n + 1, p):
                is_prime[k] = False
    return [i for i, v in enumerate(is_prime) if v]

print(sieve(20))  # [2, 3, 5, 7, 11, 13, 17, 19]