Решето Ератосфена
Решето́ Ератосфе́на в математиці — простий стародавній алгоритм знаходження всіх простих чисел менших деякого цілого числа , що був створений давньогрецьким математиком Ератосфеном.
Метод[ред. | ред. код]
Якщо потрібно знайти всі прості числа менші за певне число N, виписуються всі числа від 1 до N.
- Перше просте число - два. Викреслимо всі числа більші двох, які діляться на два (4, 6, 8 …).
- Наступне число, яке залишилося незакресленим (три), є простим. Викреслюємо всі числа більші трьох та кратні трьом (6, 9 …).
- Наступне незакреслене число (п'ять) є простим. Викреслимо всі числа більші п'яти та кратні п'яти (10, 15, 20, 25 …).
- Повторюємо операцію поки не буде досягнуто число N:
- Наступне незакреслене число є простим. Викреслимо всі числа більші нього та кратні йому.
Числа, які залишилися незакресленими після цієї процедури - прості[1].
Оцінка складності[ред. | ред. код]
Алгоритм потребує біт пам'яті та математичних операцій.
Приклад для [ред. | ред. код]
Запишемо натуральні числа від 2 до 20 в рядок:
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
Перше число в рядку 2 — просте. Викреслимо всі числа кратні 2 (кожне друге, починаючи з ):
2 34567891011121314151617181920
Наступне незакреслене число 3 — просте. Викреслимо всі числа кратні 3 (кожне третє, починаючи з ):
2 34567891011121314151617181920
Наступне незакреслене число 5 — просте. Викреслимо всі числа кратні 5 (кожне п’яте, починаючи з ). І т. д.
Необхідно викреслити кратні для всіх простих чисел , для яких . В результаті всі складені числа будуть викреслені, а залишаться всі прості числа. Для вже після викреслювання кратних числу 3 всі складені числа виявляються викресленими.
Алгоритм решета Ератосфена у вигляді програми на Python для пошуку простих чисел менших 1 000 000[ред. | ред. код]
import math
N=1000000 # діапазон в якому шукаємо прості числа
prime=[True]*N
for i in range(2,int(math.ceil(math.sqrt(N)))): # від 2 до квадратного кореня з N
if prime[i]: # якщо просте видаляємо всі числа кратні до нього
j=i*i # для j=2 будуть такі значення 4,6,8,10,12... для j=3 9,12,15,18,21...
while j<N:
prime[j]=False
j+=i
Див. також[ред. | ред. код]
Джерела[ред. | ред. код]
- ↑ Weisstein, Eric W. Sieve of Eratosthenes(англ.) на сайті Wolfram MathWorld.