Метод проверки числа на простоту при помощи алгоритма решета Эратосфена заключается в последовательном анализе возможности деления числа на стоящие до него простые числа. 4

Алгоритм позволяет найти все простые числа меньше заданного числа n. 1 Суть метода: 1

1. Взять набор чисел от 2 до n. 1
2. Вычеркнуть из набора все числа, делящиеся на 2, кроме 2. 1
3. Перейти к следующему «не отсеянному» числу — 3, снова вычеркнуть всё, что делится на 3. 1
4. Перейти к следующему оставшемуся числу — 5 и так далее до тех пор, пока не будет достигнуто число n. 1
5. После выполнения этих действий в изначальном списке останутся только простые числа. 1

Простые числа — это числа, которые делятся только на 1 и на себя, например, 2, 3, 5, 7, 11 и т. д.. 2