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

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

Введите N

показать решето

Вычислить Очистить поля
❓Инструкция

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

 

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

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

 

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

 

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

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

📖 Теория

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

 

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

 

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

 

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

 

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

 

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

 

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

 

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

 

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


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

1. Полагаем p = 2 .
2. Вычеркиваем все а ∈ [p2, N ], которые кратны p,
3. Следующее за p не вычеркнутое число обозначаем через p’.
4. Если p’2 < 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.

 

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

ℹ Заметили неточность в работе калькулятора? Убедительная просьба сообщить об этом в комментариях или через форму обратной связи. Заранее Вас благодарим.

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *