«Решето» — это один из самых ранних и элегантных алгоритмов в истории математики. Название образное: как просеивают крупу через сито, так и в этом методе «просеиваются» натуральные числа, оставляя только простые.
Метод поиска простых чисел, известный как «Решето Эратосфена», действительно придумал Эратосфен из Кирены — выдающийся древнегреческий учёный, живший примерно в 276–194 гг. до н. э.
Он был не только математиком, но и:
Географом (считается «отцом географии», первым ввёл термин «география»),
Астрономом (точно измерил окружность Земли с поразительной для своего времени точностью),
Библиотекарем (возглавлял знаменитую Александрийскую библиотеку),
Философом и поэтом
.
Напомним:
Простое число — это число, у которого ровно два делителя: 1 и оно само. Примеры: 2, 3, 5, 7, 11, 13... 1 —не простое и не составное!
Алгоритм
Цель: Найти все простые числа от 1 до 100.
Шаг 1: Запишем числа от 1 до 100
https://cdn1.ozone.ru/s3/multimedia-0/6319237488.jpg
Шаг 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:
https://www.frontiersin.org/files/Articles/409580/frym-06-00040-HTML/image_m/figure-2.jpg
Всего 25 простых чисел от 1 до 100.
Комментариев пока нет — может, вы будете первым?