Приветствую Вас, уважаемые читатели! Продолжаем тему простых чисел и рассмотрим сегодня, как работает первый из известных способов автоматизации нахождения простых чисел - решето Эратосфена. Поехали!
Решето Эратосфена - это алгоритм, который позволяет фильтровать простые числа (не имеющие делителей кроме самого себя и единицы) и составные (все остальные). Название "решето" произошло из-за того, что древние греки писали числа на дощечках, покрытых восков и делали отверстия в тех местах, где оказывались простые числа. Посмотрим, как размышляли древнегреческие математики:
1. Выписываем числа от 2 до 15 в ряд (цифру 1 пропускаем - у неё особые отношения с миром простых чисел)
2. Берем число 2 и зачеркиваем в ряду все числа, которые на него делятся: 4,6,8,10,12,14.
3. Повторяем этот процесс с числами 3,5 и понимаем, что вычеркивать больше нечего.
4. Получаем простые числа 2,3,5,7,11,13. Готово!
А вот так выглядит этот процесс в движении:
Конечно, за тысячи лет математики придумали большое количество вариаций алгоритма Эратосфена - намного увеличили его скорость и уменьшили затраты памяти, однако в истории решето Эратосфена останется первым и непревзойденным!
Читайте, как Евклид доказал, что простых чисел - бесконечное количество!
Ставьте лайк и подписывайтесь! ! ССЫЛКА НА ДЗЕН-КАНАЛ и TELEGRAM.
Второй проект - канал "Русский язык не для всех".
