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

Решето Эратосфена — это алгоритм нахождения всех простых чисел, не превышающих заданное натуральное число \( n \). Относится к классу решётчатых методов, основанных на последовательном отсеивании составных чисел из начального списка натуральных чисел. Назван в честь древнегреческого математика, астронома и географа Эратосфена Киренского (III век до н. э.), который впервые описал этот метод.

История

Первое известное описание решета Эратосфена содержится в «Введении в арифметику» Никомаха Геразского (I—II века н. э.). Сам Эратосфен не оставил письменного трактата с изложением алгоритма; сведения о нём дошли через труды поздних античных авторов, в частности, через комментарии к «Началам» Евклида. В Средние века метод был известен арабским математикам, а в Европе его популяризировал в XIII веке Леонардо Пизанский (Фибоначчи) в своей «Книге абака».

Современное название «решето Эратосфена» закрепилось в XVII веке благодаря работам французского математика Марина Мерсенна, который использовал этот метод для поиска простых чисел. В XIX веке алгоритм был формализован в рамках теории чисел, а в XX веке адаптирован для компьютерных вычислений.

Принцип работы

Алгоритм основан на следующем свойстве: любое составное число \( m \) имеет хотя бы один простой делитель, не превышающий \(\sqrt{m}\). Поэтому для нахождения всех простых чисел до \( n \) достаточно вычеркнуть из списка чисел от 2 до \( n \) все числа, кратные каждому простому числу, не превышающему \(\sqrt{n}\).

Пошаговое описание

1. Создание списка: выписываются все целые числа от 2 до \( n \) включительно.
2. Выбор первого невычеркнутого числа: первое число в списке (2) является простым.
3. Вычёркивание кратных: все числа, кратные выбранному простому числу, начиная с его квадрата (так как меньшие кратные уже вычеркнуты), помечаются как составные.
4. Повторение: выбирается следующее невычеркнутое число (3), и процесс повторяется.
5. Остановка: алгоритм завершается, когда следующее невычеркнутое число превышает \(\sqrt{n}\). Все оставшиеся невычеркнутыми числа являются простыми.

Пример для \( n = 30 \)

Исходный список: 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30.

• Шаг 1: простое число 2. Вычёркиваются кратные 2, начиная с \(2^2 = 4\): 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30.
• Шаг 2: следующее невычеркнутое — 3. Вычёркиваются кратные 3, начиная с \(3^2 = 9\): 9, 12, 15, 18, 21, 24, 27, 30. (12, 18, 24, 30 уже вычеркнуты).
• Шаг 3: следующее невычеркнутое — 5. Вычёркиваются кратные 5, начиная с \(5^2 = 25\): 25, 30.
• Шаг 4: следующее невычеркнутое — 7. \(7^2 = 49 > 30\), алгоритм останавливается.

Оставшиеся невычеркнутыми числа: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29. Это все простые числа, не превышающие 30.

Реализация

Псевдокод

`` алгоритм Решето_Эратосфена(n): // Создаём булевый массив is_prime[0..n], изначально все элементы true is_prime[0] = false is_prime[1] = false для p от 2 до sqrt(n): если is_prime[p] == true: // Вычёркиваем кратные p, начиная с p^2 для i от p*p до n с шагом p: is_prime[i] = false // Возвращаем список всех p, где is_prime[p] == true вернуть [p для p от 2 до n, если is_prime[p]] ``

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

``python def sieve_of_eratosthenes(n): if n < 2: return [] 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 i in range(p * p, n + 1, p): is_prime[i] = False return [i for i, prime in enumerate(is_prime) if prime] ``

Оптимизации

• Начало с квадрата: как показано в описании, вычёркивание кратных начинается с \(p^2\), так как все меньшие кратные уже обработаны предыдущими простыми числами.
• Шаг 2 для чётных чисел: после обработки числа 2 все чётные числа можно исключить из дальнейшего рассмотрения, обрабатывая только нечётные числа. Это сокращает объём памяти и количество операций вдвое.
• Битовые массивы: для экономии памяти вместо булевого массива можно использовать битовые поля, где каждый бит соответствует одному числу.
• Сегментированное решето: для работы с большими \( n \) (например, \(10^{12}\) и более) используется разбиение диапазона на сегменты, что позволяет уложиться в доступную оперативную память.

Сложность

Временная сложность

В классической реализации временная сложность алгоритма составляет \(O(n \log \log n)\). Это достигается за счёт того, что каждое составное число вычёркивается столько раз, сколько у него простых делителей, а суммарное количество операций вычёркивания равно \(n \sum_{p \le \sqrt{n}} \frac{1}{p} \approx n \log \log n\).

Пространственная сложность

Пространственная сложность составляет \(O(n)\) для хранения булевого массива. При использовании оптимизаций (например, только нечётные числа) требуется \(O(n/2)\) памяти.

Применение

Решето Эратосфена используется в:

• Теории чисел: для генерации таблиц простых чисел, проверки гипотез (например, гипотезы Гольдбаха), факторизации чисел.
• Криптографии: в алгоритмах генерации ключей (например, RSA) требуется нахождение больших простых чисел; решето применяется на этапе предварительного отбора кандидатов.
• Вычислительной математике: в задачах, связанных с разложением чисел на множители, поиском взаимно простых чисел, вычислением функции Эйлера.
• Образовании: как классический пример алгоритма для изучения основ программирования, работы с массивами и оценки сложности.

Вариации и обобщения

• Решето Сундарама: альтернативный алгоритм, работающий с нечётными числами и имеющий сложность \(O(n \log n)\).
• Решето Аткина: более современный алгоритм с асимптотической сложностью \(O(n / \log \log n)\), основанный на квадратичных формах.
• Решето для простых чисел-близнецов: модификация, позволяющая одновременно находить пары простых чисел, отличающихся на 2.
• Решето для чисел специального вида: например, для чисел Мерсенна или чисел Ферма.

Интересные факты

• В древности решето Эратосфена использовалось для нанесения простых чисел на папирус или восковые таблички; числа вычёркивались, а оставшиеся точки напоминали решето — отсюда название.
• Самый большой диапазон, для которого было вычислено решето Эратосфена на обычном персональном компьютере, превышает \(10^{10}\) чисел.
• Алгоритм является одним из немногих, возраст которых превышает 2000 лет, и при этом он остаётся практически применимым в современных вычислениях.
• В 2013 году математик Джеймс Мейнард (Великобритания) использовал модифицированное решето для доказательства существования бесконечного числа простых чисел, разность между которыми не превышает 600.

Источники

• Никомах Геразский. «Введение в арифметику» (II век н. э.).
• Дональд Кнут. «Искусство программирования», том 2: «Получисленные алгоритмы» (3-е издание, 1997).
• Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн. «Алгоритмы: построение и анализ» (3-е издание, 2013).
• Эрик В. Вайсштейн. «Решето Эратосфена» — MathWorld (Wolfram Research).
• Официальная документация Python: примеры алгоритмов.