Благодаря Эратосфену у нас есть таблица простых чисел. А так как таблицу свою он делал на дощечке, то убирая простые числа, у него получилось подобие "решета" ... простые числа оставались, составные убирались....
например:
найти все простые числа до n, используя метод Эратосфена
n = 20
выписываем все числа от 2 до 20
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 10
2 - простое... вычеркиваем числа, которые делятся на 2 ( я их выделю)
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
3 - простое... вычеркиваем числа, которые делятся на 3
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
5 - простое, вычеркиваем числа, кратные 5
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
а теперь как будет выглядеть решетка Эратосфена ( только выделенные числа должны быть зачеркнуты)
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
видим, что благодаря)) решетке, у нас остались простые числа (составные мы вычеркнули)
2 3 7 11 13 17 19