Решето Эратосфена
Одним из способов нахождения простых чисел, является метод, который называется «Решето Эратосфена». Онлайн разложение числа на простые множители можно провести здесь. Чтобы узнать что такое простые числа, просто прочитай эту статью.
Число называется простым, если оно делится только на 1 и само себя
Вроде бы всё просто. но недостатком является то, что нет математической формулы, которое позволяет убедиться, является число простым или нет.
Представьте число 191 587.Не существует формулы, чтобы определить, является ли оно простым!
Для этого нужно определить, есть ли в нем делители и, следовательно, составные.
Легко проверить, имеют ли первые несколько простых чисел (2, 3, 5, 7, 11) делители, используя критерии делимости. Но это не так просто для больших чисел.
Представьте, что нужно проверить все делители такого большого числа! Это очень сложно! Но есть быстрый способ определения простых чисел, который разработан греческим математиком Эратосфеном (3 век до н.э.). Этот метод называется «Решето Эратосфена». Рассмотрим, как это работает, найдя все простые числа от 1 до 100 .
Идея состоит в том, чтобы найти в таблице числа, кратные простым числам и отбросить их как составные. Числа, которые остались, будут простыми числами.
Решето Эратосфена останавливается, когда квадрат числа, которое мы тестируем, больше, чем последнее число в сетке (в нашем случае 100).
Поскольку 11 в квадрате равно 121 и 121 > 100, когда мы доберемся до числа 11, мы можем перестать смотреть.
Простые числа от 1 до 100 с решетом Эратосфена.
Начнем с размещения чисел от 1 до 100 в таблице, подобной этой.
Таким образом, очень легко создавать шаблоны, которые делают для нахождения простых чисел.
Сначала выделяем единицу, которая не является простым числом.
Далее мы ищем числа, кратные 2 и зачеркиваем их (оставляя 2, так как мы знаем, что он имеет только делители 1 и 2 и, следовательно, является простым). Все зачеркнутые числа будут составными.
Для наглядности я буду зачеркнутые составные числа делать светлым цветом.
Теперь из оставшихся чисел мы ищем кратные 3 и зачеркиваем их (кроме 3, поскольку оно простое). Простой способ сделать это, считая по три.
Делаем числа, кратные трем, светлым цветом и оставшихся чисел станет еще меньше.
Теперь пришло время искать кратные 5 . Нам не нужно искать кратные 4, потому что все кратные 4 также кратны 2, поэтому мы уже зачеркнули их. Легко найти кратные 5, все они заканчиваются на 0 или 5. Мы не зачеркиваем 5, потому что это простое число.
Зачеркнутые числа снова делаем светлым цветом.
Давайте перейдем к коэффициентам 7 (число 6 = 2 x 3, а значит оно составное и мы уже нашли кратные 2 и 3). Мы не зачеркиваем 7, так как это простое число. Кратных семи всего в таблице осталось 3 числа — это 49, 77 и 91. Зачеркиваем их.
И опять же для наглядности изменяю цвет зачеркнутых чисел.
Должны ли мы искать кратные 8, 9 и 10? Поскольку эти числа составные и кратны числам, которые мы уже искали, мы можем перейти к цифре 11. Мы уже установили, что остановимся на цифре 11, так что это означает, что мы закончили!
Список простых чисел от 1 до 100
Поэтому мы можем определить, что числа, которые мы не зачеркнули или которые синего и красного цветов, являются простыми числами. Итак, теперь у нас есть список простых чисел от 1 до 100:
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89 и 97.
Видите, как легко с помощью этого метода искать простые числа!