Решето Эратосфена — алгоритм нахождения простых чисел до заданного натурального числа путём постепенного отсеивания составных чисел. 25

В программировании алгоритм можно реализовать, поместив натуральные числа до числа N в массив. 25 В процессе выполнения алгоритма обнаруженные сложные числа заменяют нулями. 25 После выполнения алгоритма те ячейки массива, которые не содержат нули, содержат простые числа, которые выводятся на экран. 25

Чтобы найти все простые числа не больше заданного числа N, нужно выполнить следующие шаги: 3

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

Алгоритм можно реализовать на разных языках программирования, например на C, Python, C++ 123.