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

Решето Эратосфена — алгоритм нахождения всех простых чисел до некоторого целого числа n.

Для нахождения всех простых чисел не больше заданного числа n, следуя методу Эратосфена, нужно выполнить следующие шаги:

1. Выписать подряд все целые числа от двух до n (2, 3, 4, …, n).

2. Пусть переменная p изначально равна двум — первому простому числу.

3. Зачеркнуть в списке числа от 2p до n считая шагами по p (это будут числа кратные p: 2p, 3p, 4p, …).

4. Найти первое незачёркнутое число в списке, большее чем p, и присвоить значению переменной p это число.

5. Повторять шаги 3 и 4, пока возможно.

Теперь все незачёркнутые числа в списке — это все простые числа от 2 до n.

На практике, алгоритм можно улучшить следующим образом. На шаге № 3 числа можно зачеркивать начиная сразу с числа p², потому что все составные числа меньше него уже будут зачеркнуты к этому времени. И, соответственно, останавливать алгоритм можно, когда p²станет больше, чем n.Также, все p большие чем 2 — нечётные числа, и поэтому для них можно считать шагами по 2p, начиная с p².