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

Самый красивый способ найти все простые числа до заданной границы — вычеркнуть лишнее.

Простое число — натуральное число больше единицы, у которого ровно два делителя: единица и оно само.

Простые числа — это «атомы» арифметики. Любое натуральное число больше единицы либо само простое, либо однозначно раскладывается в произведение простых: $60 = 2^2 \cdot 3 \cdot 5$. Это утверждение называют основной теоремой арифметики, и именно оно делает простые числа фундаментом всей теории чисел. Прежде чем изучать их свойства, надо научиться их находить — и тут нам поможет идея, которой больше двух тысяч лет.

Зачем вычёркивать, а не делить

Наивный способ проверить число $n$ на простоту — перебрать все возможные делители. Но если нам нужны все простые до миллиона, проверять каждое по отдельности расточительно. Эратосфен Киренский, живший в III веке до нашей эры, придумал приём наоборот: вместо того чтобы спрашивать «простое ли каждое число?», он предложил вычёркивать заведомо составные.

Идея проста до гениальности. Выпишем все числа от 2 до $N$. Берём первое невычеркнутое число — это 2, оно простое. Вычёркиваем все его кратные: 4, 6, 8, … Следующее невычеркнутое — 3, тоже простое; вычёркиваем 6, 9, 12, … И так далее. То, что осталось невычеркнутым, — простые числа.

Решето в коде

Запустите и убедитесь сами:

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

primes = sieve(50)
print("Простые до 50:", primes)
print("Сколько их:", len(primes))

Вывод:

Простые до 50: [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]
Сколько их: 15

Как работает под капотом

Два момента делают решето быстрым. Во-первых, вычёркивание кратных начинаем не с $2p$, а с $p^2$: все меньшие кратные ($2p, 3p, \dots$) уже вычеркнуты предыдущими простыми. Во-вторых, внешний цикл идёт лишь пока $p^2 \le N$, то есть до $\sqrt{N}$. Если бы у числа $n \le N$ был делитель больше $\sqrt{N}$, то парный к нему делитель был бы меньше $\sqrt{N}$ и число уже было бы вычеркнуто.

Суммарное число операций оценивается величиной

$$\sum_{p \le N,\; p \text{ простое}} \frac{N}{p} \approx N \ln \ln N,$$

то есть почти линейно по $N$ — отсюда и репутация «очень быстрого» алгоритма. Сравните с наивной проверкой каждого числа делением до корня: там получается порядка $N \sqrt{N}$ операций.

Частые ошибки

Первая ловушка — забыть, что 0 и 1 не простые: единица имеет лишь один делитель, и если её посчитать простой, рухнет однозначность разложения. Вторая — стартовать вычёркивание с $2p$ вместо $p^2$: код останется верным, но потеряет в скорости. Третья — спутать «простое» и «нечётное»: 9 нечётно, но составно ($9 = 3 \cdot 3$), а 2 — единственное чётное простое.

Итог

• Простое число имеет ровно два делителя; 1 — не простое.
• Решето Эратосфена вычёркивает кратные каждого найденного простого.
• Достаточно перебирать $p$ до $\sqrt{N}$ и вычёркивать с $p^2$.
• Сложность около $N \ln \ln N$ — практически линейна.