Здравствуйте, дорогие читатели! Можете ли Вы сразу определить, является ли число 101 - простым? Или быстро перечислить все простые числа, меньше 102? Если да, то Вы почти наверняка пользуетесь алгоритмом, который сформулировал греческий математик Эратосфен еще до нашей эры. Если вдруг, Вы используете другой способ, то поделитесь им в комментариях.
Удивительно, но этот алгоритм популярен до сих пор. И сегодня, мы разберемся, как пользоваться тем, что называется решетом Эратосфена.
Занимательно, что поисковик так и норовит подсунуть портрет Евклида, вместо портрета Эратосфена. Хотя, про Евклида и его алгоритм, я уже написала две статьи. Ну, раз великий интернет настаивает, то в конце этой публикации прикреплю ссылку на статью про алгоритм Евклида. Там можно полюбоваться его портретом
Вы находитесь на канале Trifler, где я разбираю интересные математические задачи, а также рассуждаю на некоторые околоматематические темы. Если Вы искренне увлечены математикой, но еще не подписаны на этот канал, то самое время это исправить и вступить в наши ряды! Подписаться
Решето Эратосфена
Название, на самом деле, говорящее. Эратосфен, действительно, отбирал простые числа при помощи своеобразного решета.
Конечно, постоянные читатели моего канала знают, что такое простые числа. Но, возможно эта статья попадется на глаза кому-то менее информированному, поэтому напомню:
Натуральное число, большее единицы, называют простым, если оно имеет всего два натуральных делителя: единицу и само это число
Чтобы выделять простые числа, не превосходящие число n, Эратосфен предложил такой алгоритм:
При таком подходе, те числа, которые останутся не вычеркнутыми и будут являться простыми.
На самом деле, им можно пользоваться и для выделения простых чисел из какого-то отрезка натурального ряда, начинающегося не с единицы.
Ну что ж, посмотрим это на примере и вместе ответим на вопросы, которые я задала Вам в начале статьи.
Пример
Задание на картинке:
Выполняем первый шаг алгоритма: записываем все числа от 2 до 102 в порядке возрастания. Можно записывать и вместе с единицей, но нужно помнить, что она не является простым числом.
Вычеркиваем все четные числа, кроме двойки, так как они кратны двум:
Вычеркиваем числа, кратные трем, кроме тройки:
Давайте выясним, до каких пор этот процесс будет продолжаться:
Получается, что вычеркивание будет продолжаться до тех пор, пока мы не вычеркнем числа кратные 10. Далее, я подробно не буду описывать каждый шаг. Суть уже ясна. И, не забываем зачеркнуть единицу.
При чем, задача упрощается, так как, например, числа кратные четырем, шести, восьми и десяти уже вычеркнуты. Ведь они также кратны и двум. По сути, остается вычеркнуть только те числа, которые кратны простым числам, находящимся в промежутке от 4 до 10.
Таким образом, те числа, которые остались не вычеркнутыми и будут являться простыми. Давайте выпишем их:
Вот мы и получили ответ.
Если Вам понравилась статья, то обязательно ставьте лайки и комментируйте ее. Это поспособствует тому, чтобы ее увидело много людей!
Ссылка на статью про алгоритм Евклида, в которой можно полюбоваться его портретом:
Как Евклид находил наибольший общий делитель. Простейший способ