Решето Эратосфена: алгоритм, пример и код Python

Короткий ответ. Решето Эратосфена находит все простые числа от 2 до заданного n. Нужно взять очередное невычеркнутое число p, оставить его как простое и отметить его кратные как составные. Вычёркивание можно начинать с p², а закончить, когда p² > n; все оставшиеся числа будут простыми.

Этот алгоритм удобен, когда нужен не ответ для одного числа, а полный список простых чисел до некоторой границы. Вместо отдельной проверки каждого числа на делимость решето последовательно убирает целые ряды кратных.

Что такое решето Эратосфена

Простое число имеет ровно два различных натуральных делителя: 1 и само число. Например, 2, 3, 5 и 7 простые. Составное число имеет больше двух делителей и раскладывается в произведение меньших натуральных чисел: 6 = 2 · 3. Число 1 не является ни простым, ни составным.

Решето работает с таблицей чисел от 2 до n. Первое невычеркнутое число объявляют простым, затем вычёркивают его кратные. Процесс повторяют для следующего невычеркнутого числа. Название передаёт идею метода: составные числа как будто проходят сквозь решето, а простые остаются.

Как выполнить решето по шагам

1. Запишите все целые числа от 2 до выбранной границы n.
2. Возьмите первое невычеркнутое число. В начале это 2. Оно простое.
3. Вычеркните кратные этого числа, не вычёркивая само число.
4. Перейдите к следующему невычеркнутому числу. Оно тоже простое, поскольку не делится ни на одно меньшее простое.
5. Повторяйте вычёркивание, пока квадрат текущего простого числа не станет больше n.
6. Выпишите все числа, которые не были вычеркнуты.

Пример: простые числа до 30

1. p = 2. Оставляем 2 и вычёркиваем 4, 6, 8, 10, …, 30.
2. p = 3. Оставляем 3. Число 6 уже вычеркнуто, поэтому новые вычёркивания можно начать с 9: 9, 12, 15, …, 30.
3. p = 5. Число 5 не вычеркнуто, значит оно простое. Начинаем с 25. Следующее кратное 30 уже отмечено.
4. Число 6 вычеркнуто, а 7² = 49 > 30. На этом обработку можно закончить.

Остаются 2, 3, 5, 7, 11, 13, 17, 19, 23 и 29. В списке десять простых чисел.

Почему алгоритм даёт правильный ответ

Нужно проверить два утверждения: ни одно простое число не будет вычеркнуто, а каждое составное будет.

1. Простые сохраняются. Мы вычёркиваем только числа вида p · k, где k ≥ 2. Такое число имеет делители p и k, поэтому оно составное. Само p не вычёркивается.
2. Составные удаляются. Возьмём наименьший простой делитель p составного числа m и запишем m = p · k. Тогда k ≥ p, иначе у k нашёлся бы простой делитель меньше p. Поэтому m ≥ p² и при обработке p число m обязательно окажется среди вычёркиваемых кратных.

Следовательно, после завершения решета невычеркнутыми остаются все простые и только простые числа.

Почему вычёркивание начинается с p²

На шаге p кратные 2p, 3p, …, (p−1)p уже обработаны. У каждого такого произведения есть множитель меньше p, а значит, оно было вычеркнуто при обработке меньшего простого делителя. Первым кратным, которое ещё может быть не отмечено, является p · p = p².

Например, при p = 7 числа 14, 21, 28, 35 и 42 уже вычеркнуты на шагах 2, 3 или 5. Новую работу шаг 7 начинает с 49. Начать с 2p тоже допустимо: ответ останется правильным, но алгоритм будет повторять лишние действия.

Почему достаточно проверить p² ≤ n

Пусть составное число m представлено как a · b. Если бы оба множителя были больше √m, то их произведение оказалось бы больше m. Поэтому хотя бы один множитель любого составного числа не превышает его квадратного корня. У этого множителя, в свою очередь, есть простой делитель не больше √m.

Когда p² > n, каждое составное число до n уже имело меньший простой делитель и было вычеркнуто. При n = 49 равенство имеет значение: шаг p = 7 должен отметить 49. Поэтому в коде условие записывают как p * p <= n, а не как строгое неравенство.

Алгоритм в псевдокоде

создать is_prime[0..n] со значением true
is_prime[0] = false
is_prime[1] = false

p = 2
пока p * p <= n:
    если is_prime[p]:
        для multiple от p * p до n с шагом p:
            is_prime[multiple] = false
    p = p + 1

вывести все i от 2 до n, где is_prime[i] = true

Массив is_prime хранит состояние каждого числа. Значение true означает «пока считается простым», а false — «точно составное» или не входящее в область простых чисел. Проверка is_prime[p] нужна, чтобы не запускать отдельный проход для уже вычеркнутого составного p.

Реализация на Python

def sieve(n: int) -> list[int]:
    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 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]]

Массив имеет длину n + 1, потому что индекс n должен существовать. Верхняя граница в range тоже равна n + 1, иначе само число n не попадёт в перебор. Для sieve(10) функция вернёт [2, 3, 5, 7], а для 0 и 1 — пустой список.

Чем решето отличается от перебора делителей

При проверке простоты одного числа достаточно попробовать делители до его квадратного корня. Этот способ хорош для отдельного m, поскольку не требует массива длины m. Но если последовательно проверять каждое число от 2 до n, многие операции деления повторятся.

Решето решает другую задачу: строит сразу весь список простых до n. Один проход по кратным двойки отмечает все чётные составные, проход по кратным тройки — ещё одну группу чисел. Поэтому для массового поиска решето обычно эффективнее. Выбор метода зависит от запроса: одно число проверяют тестом простоты, полный диапазон обрабатывают решетом.

Сложность и границы применения

Базовая версия требует O(n) памяти, а время работы оценивается как O(n log log n). Такая оценка получается потому, что для простого p алгоритм проходит примерно по n/p кратным, а сумма обратных простых чисел до n растёт как log log n.

Обычное решето подходит для таблицы всех простых до умеренной границы. Если нужно обработать большой отрезок [L, R], а хранить массив от 0 до R слишком дорого, применяют сегментированное решето. Для проверки одного очень большого числа используют специализированные тесты простоты. Базовое решето не предназначено для прямой генерации современных криптографических ключей.

Где применяют решето и простые числа

• Учебные задачи. Решето помогает увидеть разницу между простыми и составными числами, кратными и делителями.
• Разложение на множители. Заранее найденные простые используют как возможные делители.
• Алгоритмические задачи. Таблица простых нужна для подсчёта делителей, вычисления функции Эйлера и обработки большого числа запросов.
• Криптография. Простые числа играют центральную роль во многих системах, но решето малой границы обычно служит вспомогательным инструментом, а не создаёт секретные ключи.

Практический пример: если программа должна тысячу раз отвечать, простое ли число не больше миллиона, выгодно один раз построить решето, а затем получать каждый ответ обращением к элементу массива.

Кто такой Эратосфен

Эратосфен Киренский жил примерно в 276–194 годах до н. э. и возглавлял Александрийскую библиотеку. Он занимался математикой, астрономией и географией. Его имя также связано с вычислением длины земного меридиана по углу падения солнечных лучей в двух городах.

Алгоритм просеивания простых чисел традиционно называется решетом Эратосфена. Метод ценен не только возрастом: в нём хорошо видна важная идея программирования — вместо повторной проверки каждого объекта один раз отметить все заведомо неподходящие.

Типичные ошибки

• Оставить 1 в ответе. Вывод простых чисел начинается с 2.
• Вычеркнуть само p. Число p уже признано простым; вычёркивают его кратные начиная с p².
• Остановиться при p² < n. Для квадратной границы нужно условие p² ≤ n, иначе можно пропустить p².
• Не включить n. И массив, и цикл вычёркивания должны охватывать верхнюю границу.
• Обрабатывать составное p. Перед внутренним циклом проверяют, осталось ли p невычеркнутым.
• Считать решето тестом одного числа. Для одного большого числа массив от 0 до n часто расходует память без необходимости.

Задачи для самопроверки

1. Выполните решето до 25 и выпишите все простые числа.
2. Какие новые числа будут вычеркнуты на шаге p = 5 при n = 60?
3. Почему при p = 7 и n = 100 можно начать с 49?
4. Какое условие цикла не позволит пропустить число 49?
5. Что вернёт приведённая функция для n = 0, n = 1 и n = 2?
6. Простое ли число 91 и на каком шаге решета оно будет вычеркнуто?
7. До какого простого числа включительно нужно выполнять шаги для n = 200?
8. Объясните, почему старт внутреннего цикла с 2p не меняет ответ, но замедляет работу.

Ответы и пояснения

1. 2, 3, 5, 7, 11, 13, 17, 19 и 23.
2. 25, 35 и 55. Числа 30, 40, 45, 50 и 60 уже отмечены на шагах 2 или 3.
3. Меньшие кратные 7 уже имеют простой множитель 2, 3 или 5 и вычеркнуты.
4. p * p <= n.
5. [], [] и [2].
6. 91 = 7 · 13, поэтому число составное; оно будет вычеркнуто на шаге 7.
7. До 13 включительно, потому что 13² = 169 ≤ 200, а 17² = 289 > 200.
8. Все кратные всё равно будут отмечены, но часть из них алгоритм посетит повторно.

Частые вопросы

До какого числа нужно вычёркивать кратные?

Нужно обрабатывать простые p, пока p² ≤ n. Например, для n = 100 достаточно шагов 2, 3, 5 и 7. Следующее простое 11 уже даёт 11² = 121 > 100.

Почему 1 не простое число?

У простого числа ровно два различных натуральных делителя. У единицы только один делитель. Такое определение также сохраняет единственность разложения натурального числа больше 1 на простые множители.

Можно ли начать вычёркивать с 2p?

Да, список простых получится правильным. Однако кратные меньше p² уже были обработаны на предыдущих шагах, поэтому начало с 2p добавляет повторную работу.

Какие простые числа до 30?

Это 2, 3, 5, 7, 11, 13, 17, 19, 23 и 29. Число 1 в список не входит.

Чем решето отличается от проверки простоты?

Решето строит полный список простых до n. Тест простоты отвечает на вопрос об одном конкретном числе и может не хранить таблицу всего диапазона.

Почему простые числа не заканчиваются?

Предположим, что перечислены все простые числа. Перемножим их и прибавим 1. Новое число не делится ни на одно простое из списка без остатка, поэтому оно либо простое, либо имеет новый простой делитель. Получается противоречие: конечного списка всех простых быть не может.

Что изучать дальше

Перед этой темой полезно повторить простые и составные числа. Затем можно перейти к разложению на простые множители и применить найденные простые числа при вычислении НОД и НОК.

Простые числа — начало исследования закономерностей. Посмотрите программу курса «Теория чисел» и выберите следующую тему после решета. Пример кода и тренажёр выше доступны без регистрации.

Материал подготовлен редакцией STEMskills. Об образовательном проекте.