Решето́ Ератосфе́на в математиці — алгоритм пошуку всіх простих чисел, менших заданого цілого числа , створений давньогрецьким математиком Ератосфеном.
Метод
Якщо потрібно знайти всі прості числа менші за певне число N, виписуються всі числа від 2 до N. Перше просте число — два. Викреслимо всі числа більші двох, які діляться на два (4, 6, 8 …). Наступне число, яке залишилося незакресленим (три), є простим. Викреслюємо всі числа більші трьох та кратні трьом (6, 9 …). Наступне незакреслене число (п'ять) є простим. Викреслимо всі числа більші п'яти та кратні п'яти (10, 15, 20, 25 …). Повторюємо операцію поки не буде досягнуто число N: Наступне незакреслене число є простим. Викреслимо всі числа більші нього та кратні йому. Числа, які залишилися незакресленими після цієї процедури — прості.
Викреслювати кратні для кожного простого p можна розпочинаючи з p2, а не з 2p. Тобто: кратні трьом викреслюють починаючи з 32=9 (оскільки 6 уже викреслено як кратне двом); кратні п'яти викреслюють починаючи з 25=52 (числа 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 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
Наступне незакреслене число 3 — просте. Викреслимо всі числа кратні 3 (кожне третє, починаючи з ):
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
Наступне незакреслене число 5 — просте. Викреслимо всі числа кратні 5 (кожне п'яте, починаючи з ). І т. д.
Необхідно викреслити кратні для всіх простих чисел , для яких . В результаті всі складені числа будуть викреслені, а залишаться всі прості числа. Для вже після викреслювання кратних числу 3 всі складені числа виявляються викресленими.
Реалізація алгоритму решета Ератосфена
Псевдокод Решето Ератосфена може бути виражене в псевдокоді наступним чином, p. 16.:
Алгоритм Решето Ератосфена є вхід : ціле число n > 1. вихід : всі прості числа від 2 до n.
нехай A — масив булевих значень, індексованих цілим числом s від 2 до n, ініціалізуємо весь масив значеннями true.
для i = 2, 3, 4, ..., що не перевищує робити якщо А [i] є true для j = i2, i2 + i, i2 + 2i, i2 + 3i, ..., що не перевищує n робити A[j] := false
повернути всі i де A[i] є true.
Цей алгоритм видає всі прості числа, що не перевищують . Він включає загальну оптимізацію, яка полягає в тому, щоб почати перераховувати числа кратні кожному простому з . Часова складність цього алгоритму становить , при стандартному припущенні, що оновлення масиву відбувається за час .
Python Реалізація мовою Python: import math N = 1000000 # діапазон в якому шукаємо прості числа prime = [True] * N prime, prime = 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
Оцінка складності Алгоритм потребує біт пам'яті та математичних операцій.
Порівняння з іншими методами Попри свою простоту, алгоритм є вельми ефективним. Лише у другій половині XX-го сторіччя, із розвитком комп'ютерної техніки та програмування було винайдено асимптотично кращі методи. Однак, вони складніші й їх перевага виявляється лише для досить великих чисел. До N ~ 104—105 решето Ератосфена залишається найкращим.
Див. також Решето Сундарама Решето Аткіна
Джерела