Решето Ератосфе на в математиці простий стародавній алгоритм знаходження всіх простих чисел менших деякого цілого числа

Решето́ Ератосфе́на в математиці — простий стародавній алгоритм знаходження всіх простих чисел менших деякого цілого числа $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 вже викреслено як кратні двом, трьом чи п'яти;
і т.д.

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

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

Приклад

Запишемо натуральні числа від 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

Див. також

Джерела

Weisstein, Eric W. Sieve of Eratosthenes(англ.) на сайті Wolfram MathWorld.
Jonathan Sorenson, An Introduction to Prime Number Sieves, Computer Sciences Technical Report #909, Department of Computer Sciences University of Wisconsin-Madison, January 2, 1990 (the use of optimization of starting from squares, and thus using only the numbers whose square is below the upper limit, is shown).
Sedgewick, Robert (1992). Algorithms in C++. Addison-Wesley. ISBN ., p. 16.

[1] Weisstein, Eric W. Sieve of Eratosthenes(англ.) на сайті Wolfram MathWorld.

[intro-2] Jonathan Sorenson, An Introduction to Prime Number Sieves, Computer Sciences Technical Report #909, Department of Computer Sciences University of Wisconsin-Madison, January 2, 1990 (the use of optimization of starting from squares, and thus using only the numbers whose square is below the upper limit, is shown).

[sedgewick-3] Sedgewick, Robert (1992). Algorithms in C++. Addison-Wesley. ISBN ., p. 16.