Что такое решето Эратосфена? (кратко)

Выписываются числа от 1 до ... n

1 не будет входит в решетку

2 - простое число, далее зачеркиваем все числа, которые делятся на 2

3 - простое, зачеркиваем, все числа, которые делятся на 3

5 - простое, зачеркиваем числа, кратные 5

7 - простое, зачеркиваем числа, кратные 7 ... и т. д.

таким образом, все зачеркнутые числа - это составные, остаются только простые числа, которые делятся на 1 и на себя