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

Решето́ Ератосфе́на в математиці — простий стародавній алгоритм знаходження всіх простих чисел менших деякого цілого числа Неможливо розібрати вираз (синтаксична помилка): {\displaystyle n</math. == Метод == [[Файл:Sieve_of_Eratosthenes_animation.gif|right]] Якщо потрібно знайти всі прості числа менші за певне число N, виписуються всі числа від 1 до N. # Перше просте число - два. Викреслимо всі числа більші двох, які діляться на два (4, 6, 8 …). # Наступне число, яке залишилося незакресленим (три), є простим. Викреслюємо всі числа більші трьох та кратні трьом (6, 9 …). # Наступне незакреслене число (п'ять) є простим. Викреслимо всі числа більші п'яти та кратні п'яти (10, 15, 20, 25 …). # Повторюємо операцію поки не буде досягнуто число N: #* Наступне незакреслене число є простим. Викреслимо всі числа більші нього та кратні йому. Числа, які залишилися незакресленими після цієї процедури - прості<ref>{{MathWorld|SieveofEratosthenes|Sieve of Eratosthenes}}</ref>. == Оцінка складності == Алгоритм потребує <math>O(N)} біт пам'яті та $O(N\log \log N))$ математичних операцій.

Приклад для $n=20$

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

Алгоритм решета Ератосфена у вигляді програми на псевдокоді для пошуку простих чисел менших
1 000 000

limit = 1000000
// початково вважаємо, що всі числа прості
// присвоєння змінній типу стрічка символів ''sieve$''  рядка, який складається з 1000000 літер "Р",
sieve$ = string of the character "P" with length limit

prime = 2  // 2 – перше просте число

repeat while prime² < limit 
// зміна літер "Р", порядковий номер (індекс) яких кратний ''prime'' (за виключенням індекса ''prime''), на "N" 
set the character at the index of each multiple of ''prime'' (excluding index ''prime'' * 1) in ''sieve$'' to "N"
// змінній ''prime'' присвоюється індекс наступної "Р" в стрічці ''sieve$''
prime = index of the next instance of "P" in ''sieve$'' after index ''prime''
end repeat

Див. також

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