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

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

Для знаходження всіх простих чисел, не більших від заданого числа n, дотримуючись методу Ератосфена, потрібно виконати наступні кроки:
1. Виписати підряд всі цілі числа від двох до n (2, 3, 4, ..., n).
2. Нехай змінна p спочатку дорівнює 2 - першому простому числу.
3. Викреслити зі списку всі числа від 2p до n, які діляться на p (тобто, числа 2p, 3p, 4p, ...).
4. Знайти перше невикреслене число, більше ніж p, і присвоїти змінній p це число.
5. Повторювати кроки 3 і 4 до тих пір, поки p не стане більшим, ніж n.
6. Всі невикреслені числа в списку - прості числа.
На практиці, алгоритм можна трохи поліпшити в такий спосіб.
На кроці №3, числа можна викреслювати, починаючи відразу з числа p ² , тому що всі складені числа, які менші від нього вже будуть викреслені до цього часу. І, відповідно, зупиняти алгоритм можна, коли p ² стане більшим, ніж n.

1. Спочатку виписуються всі числа від 1 до n.
2. Перше просте число — два. 
3. Викреслимо всі числа більші двох, які діляться на два (4, 6, 8 …). 
4. Наступне число, яке залишилося незакресленим (три), є простим. 
5. Викреслюємо всі числа більші трьох та кратні трьом (6, 9 …). 
6. Наступне незакреслене число (п'ять) є простим. 
7. Викреслимо всі числа більші п'яти та кратні п'яти (10, 15, 20, 25 …). 
8. Повторюємо операцію поки не буде досягнуто число n. 
9. Наступне незакреслене число є простим. 
10. Викреслимо всі числа більші нього та кратні йому. 
11. Числа, які залишилися незакресленими після цієї процедури — прості.