Приветствую Вас, уважаемые читатели! Продолжаем тему простых чисел и рассмотрим сегодня, как работает первый из известных способов автоматизации нахождения простых чисел — решето Эратосфена. Поехали!
Источник: https://yt3.ggpht.com/a/AATXAJzvZbc7r2tjLBTuIanhXuHrWUF3d8gJ2VCSyA=s900-c-k-c0xffffffff-no-rj-mo
Решето Эратосфена — это алгоритм, который позволяет фильтровать простые числа (не имеющие делителей кроме самого себя и единицы) и составные (все остальные). Название "решето" произошло из-за того, что древние греки писали числа на дощечках, покрытых восков и делали отверстия в тех местах, где оказывались простые числа. Посмотрим, как размышляли древнегреческие математики:
1. Выписываем числа от 2 до 15 в ряд (цифру 1 пропускаем — у неё особые отношения с миром простых чисел)
2. Берем число 2 и зачеркиваем в ряду все числа, которые на него делятся: 4,6,8,10,12,14.
3. Повторяем этот процесс с числами 3,5 и понимаем, что вычеркивать больше нечего.
4. Получаем простые числа 2,3,5,7,11,13. Готово!
А вот так выглядит этот процесс в движении:
Источник: https://upload.wikimedia.org/wikipedia/commons/8/8c/New_Animation_Sieve_of_Eratosthenes.gif
Конечно, за тысячи лет математики придумали большое количество вариаций алгоритма Эратосфена — намного увеличили его скорость и уменьшили затраты памяти, однако в истории решето Эратосфена останется первым и непревзойденным!
Читайте, как Евклид доказал, что простых чисел — бесконечное количество!
Ставьте лайк и подписывайтесь! ! ССЫЛКА НА ДЗЕН-КАНАЛ и TELEGRAM.
Второй проект — канал "Русский язык не для всех".
