«Решето» — это один из самых ранних и элегантных алгоритмов в истории математики. Название образное: как просеивают крупу через сито, так и в этом методе «просеиваются» натуральные числа, оставляя только простые.
Метод поиска простых чисел, известный как «Решето Эратосфена», действительно придумал Эратосфен из Кирены — выдающийся древнегреческий учёный, живший примерно в 276–194 гг. до н. э.
Он был не только математиком, но и:
- Географом (считается «отцом географии», первым ввёл термин «география»),
- Астрономом (точно измерил окружность Земли с поразительной для своего времени точностью),
- Библиотекарем (возглавлял знаменитую Александрийскую библиотеку),
- Философом и поэтом.
Напомним:
- Простое число — это число, у которого ровно два делителя: 1 и оно само. Примеры: 2, 3, 5, 7, 11, 13… 1 — не простое и не составное!
Решето Эратосфена — это древний алгоритм для нахождения всех простых чисел до заданного числа.
Алгоритм:
- Выписываем все числа от 2 до N
- Первое непомеченное число (2) — простое
- Вычеркиваем все кратные этому числу
- Переходим к следующему непомеченному числу и повторяем шаг 3
- Продолжаем, пока не проверим все числа до √N
Найденные простые числа:
Алгоритм
Цель: Найти все простые числа от 1 до 100.
Шаг 1: Запишем числа от 1 до 100
Шаг 2: Вычёркиваем по правилам
🔹 Вычеркни число 1.
🔹 Обведи 2 — это первое простое число.
Затем вычеркни все числа, кратные 2 (то есть каждое второе): 4, 6, 8, 10, 12, 14, …, 100
🔹 Следующее число — 3. Обведи.
Вычеркни все числа, кратные 3 (после 3): 6, 9, 12, 15, 18, 21, … (уже вычеркнутые можно не трогать)
🔹Следующее число — 5. Обведи.
Вычеркни все кратные 5: 10, 15, 20, 25, 30, … (многие уже вычеркнуты)
🔹 Следующее число — 7. Обведи.
Вычеркни кратные 7: 14, 21, 28, 35, 42, 49, 56, 63, 70, 77, 84, 91, 98
🔹 Следующее число — 11. Но:
11×11=121>100 , значит, дальше ничего вычёркивать не нужно.
Шаг 3: Остались только простые числа!
Обведённые числа — это простые от 2 до 100:
Всего 25 простых чисел от 1 до 100.