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

Решето́ Ератосфе́на в математиці — алгоритм пошуку всіх простих чисел, менших заданого цілого числа $N$ , створений давньогрецьким математиком Ератосфеном.

Метод

Якщо потрібно знайти всі прості числа менші за певне число N, виписуються всі числа від 2 до N.

Перше просте число — два. Викреслимо всі числа більші двох, які діляться на два (4, 6, 8 …).
Наступне число, яке залишилося незакресленим (три), є простим. Викреслюємо всі числа більші трьох та кратні трьом (6, 9 …).
Наступне незакреслене число (п'ять) є простим. Викреслимо всі числа більші п'яти та кратні п'яти (10, 15, 20, 25 …).
Повторюємо операцію поки не буде досягнуто число N:
- Наступне незакреслене число є простим. Викреслимо всі числа більші нього та кратні йому.

Числа, які залишилися незакресленими після цієї процедури — прості.

Викреслювати кратні для кожного простого p можна розпочинаючи з p², а не з 2p. Тобто:

кратні трьом викреслюють починаючи з 3²=9 (оскільки 6 уже викреслено як кратне двом);
кратні п'яти викреслюють починаючи з 25=5² (числа 10, 15, 20 уже викреслено, бо вони кратні двом або трьом);
кратні семи починають викреслювати з 49, оскільки 14, 21, 28, 35 і 42 вже викреслено як кратні двом, трьом чи п'яти;
і т.д.

Приклад

Запишемо натуральні числа від 2 до 20 в рядок:

 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

Перше число в рядку 2 — просте. Викреслимо всі числа кратні 2 (кожне друге, починаючи з $2^{2}=4$ ):

 2 3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20

Наступне незакреслене число 3 — просте. Викреслимо всі числа кратні 3 (кожне третє, починаючи з $3^{2}=9$ ):

 2 3  4  5  6  7  8   9   10  11  12  13  14   15   16  17  18  19  20

Наступне незакреслене число 5 — просте. Викреслимо всі числа кратні 5 (кожне п'яте, починаючи з $5^{2}=25$ ). І т. д.

Необхідно викреслити кратні для всіх простих чисел $p$ , для яких $p^{2}\leq n$ . В результаті всі складені числа будуть викреслені, а залишаться всі прості числа. Для $n=20$ вже після викреслювання кратних числу 3 всі складені числа виявляються викресленими.

Реалізація алгоритму решета Ератосфена

Псевдокод

Решето Ератосфена може бути виражене в псевдокоді наступним чином:

Алгоритм Решето Ератосфена є вхід : ціле число n > 1. вихід : всі прості числа від 2 до n. нехай A — масив булевих значень, індексованих цілим числом s від 2 до n, ініціалізуємо весь масив значеннями true. для i = 2, 3, 4, ..., що не перевищує  $\sqrt n$  робити якщо А [i] є true для j = i², i² + i, i² + 2i, i² + 3i, ..., що не перевищує n робити A[j] := false повернути всі i де A[i] є true.

Цей алгоритм видає всі прості числа, що не перевищують $n$ . Він включає загальну оптимізацію, яка полягає в тому, щоб почати перераховувати числа кратні кожному простому $i$ з $i 2$ . Часова складність цього алгоритму становить $O (n log log n)$ , при стандартному припущенні, що оновлення масиву відбувається за час $O (1)$ .

Python

Реалізація мовою Python:

import math N = 1000000 # діапазон в якому шукаємо прості числа prime = [True] * N prime[0], prime[1] = False, False # 0 та 1 не є простими for i in range(2, math.ceil(math.sqrt(N))): # від 2 до квадратного кореня з N   if prime[i]: # якщо просте видаляємо всі числа кратні до нього  j = i * i # для i=2,j будуть такі значення 4,6,8,10,12... для i=3 j — 9,12,15,18,21...  while j < N:  prime[j] = False  j += i

Оцінка складності

Алгоритм потребує $O(N)$ біт пам'яті та $O(N\log \log N)$ математичних операцій.

Порівняння з іншими методами

Попри свою простоту, алгоритм є вельми ефективним. Лише у другій половині XX-го сторіччя, із розвитком комп'ютерної техніки та програмування було винайдено асимптотично кращі методи. Однак, вони складніші й їх перевага виявляється лише для досить великих чисел. До N ~ 10⁴—10⁵ решето Ератосфена залишається найкращим.

Див. також

Решето Сундарама
Решето Аткіна