Алгоритм решета Эратосфена для нахождения простых чисел заключается в постепенном отсеивании составных чисел. 34

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

1. Выписать подряд все целые числа от двух до n (2, 3, 4, …, n). 2
2. Пусть переменная p изначально равна двум — первому простому числу. 2
3. Зачеркнуть в списке числа от 2p до n, считая шагами по p (это будут числа, кратные p: 2p, 3p, 4p, …). 2
4. Найти первое незачёркнутое число в списке, большее чем p, и присвоить значению переменной p это число. 2
5. Повторять шаги 3 и 4, пока возможно. 2
6. Теперь все незачёркнутые числа в списке — это все простые числа от 2 до n. 2

Эффективность алгоритма в том, что он позволяет сократить количество проверяемых чисел, исключая кратные уже найденных простых чисел. 1