Решето Эратосфена

 Калькулятор «Решето Эратосфена» для поиска все простых чисел до введенного числа N.

 

 Использование:

 В единственное поле введите число N — до которого необходимо искать простые числа.
 Нажми на кнопку «Вычислить»
 Калькулятор построит решето Эратосфена и выдаст список всех простых чисел до N.

 

 Галочка «показать решето» позволяет выдать помимо всех простых чисел до N еще и таблицу — решето Эратосфена, в которой можно увидеть наглядно какие числа были вычеркнуты в ходе работы алгоритма, а какие остались.

 

 Ограничения калькулятора:

 Калькулятору на вход подается натуральное число от 1 до 100 000 в случае, если решето выводить не требуется.
 В случае, когда необходимо выводить также решето, алгоритм работает с натуральными числами от 1 до 10 000.

 В сегодняшнем посте мы узнаем, как найти простые числа, используя решето Эратосфена.

 

 Напомним, что число является простым, если оно делится только на 1 и на само себя. Это довольно-таки просто понять, однако недостатком является то, что нет математической формулы, чтобы убедиться, является ли число простым или нет. 

 

 Подумайте о большом числе, как 151 647. У нас нет формулы, чтобы определить, является ли это простым или нет.

 

 Мы должны выяснить, есть ли у данного числа другие делители кроме 1 и самого себя, тогда мы смогли бы сказать, что оно составное.

 

 Легко проверить, имеют ли первые несколько простых чисел (2, 3, 5, 7, 11) делители, используя критерии делимости. Но это не так просто для больших чисел.

 

 Представьте, что нужно проверить все делители такого большого числа! Это было бы сумасшествием!

 

 Решето Эратосфена

 

 Греческий математик Эратосфен (3 век до н.э.) разработал быстрый способ найти все простые числа. Этот процесс называется Сито Эратосфена . В разделе <примеры> мы посмотрим, как это работает, найдя все простые числа от 1 до 100.

 

 Идея состоит в том, чтобы найти в таблице числа, кратные числу и, следовательно, составные, чтобы отбросить их как простые. Числа, которые остались, то есть те, что мы не отбросили — будут простыми числами. Решето Эратосфена останавливается, когда квадрат числа, которое мы тестируем, больше, чем последнее число в сетке (в нашем случае 100). Поскольку 11² = 121 и 121 > 100,  поэтому, когда мы доберемся до числа 11, мы можем прекращать работу алгоритма.

 Алгоритм: (решето Эратосфена). Дано натуральное N. Нужно вычислить все простые числа, не превосходящие N.

1. Полагаем p = 2 .
2. Вычеркиваем все а ∈ [p², N ], которые кратны p,
3. Следующее за p не вычеркнутое число обозначаем через p’.
4. Если p’² < N, то полагаем p = p’ и переходим к шагу 2.
5. Невычеркнутые числа из {2, 3,…, N } образуют искомое множество простых.

Конец алгоритма.

 

 Сложность алгоритма:

Сложность алгоритма составляет

 

 

операций при составлении таблицы простых чисел до n.

 Предположим, нам необходимо найти все простые числа до 100. Построим решето Эратосфена для N = 100;

 Начнем с размещения чисел от 1 до 100 в таблице. Таким образом, очень легко увидеть кратные для каждого p числа. Мы выделяем 1, который не является простым числом.

 Сначала мы ищем кратные 2 и выделяем их (оставляя 2, так как мы знаем, что он имеет только делители 1 и 2 и, следовательно, является простым). Все выделенные числа будут составными. Таковыми являются все четные числа кроме самой двойки.

 Теперь из оставшихся чисел мы ищем кратные 3 и выделяем их (кроме 3, поскольку оно простое). Простой способ сделать это, считать по три (6, 9, 12 и так далее).

 Теперь пришло время искать кратные 5 . Нам не нужно искать кратные 4, потому что все кратные 4 также кратны 2, поэтому мы уже выделили их. Легко найти кратные 5, все они заканчиваются на 0 или 5. Мы не выделяем 5, потому что это простое число.

 Давайте перейдем к коэффициентам  7  (6 = 2 * 3, и мы уже нашли коэффициенты 2 и 3). Мы не выделяем 7, но ищем все числа кратные 7.

 Должны ли мы искать кратные 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.

 

 Видите, как легко с помощью этого метода искать простые числа!