ФЭНДОМ


Prime Эта статья является статьёй проекта «Простые числа»
Вы можете помочь проекту, развив и дополнив её.
Wikipedia Это — материал из Википедии.

Решето Эратосфена — алгоритм нахождения всех простых чисел до некоторого целого числа n, который приписывают древнегреческому математику Эратосфену Киренскому.

Алгоритм Править

Animation Sieb des Eratosthenes

Для нахождения всех простых чисел не больше заданного числа n, следуя методу Эратосфена, нужно выполнить следующие шаги:

  1. Выписать подряд все целые числа от двух до n (2, 3, 4, …, n).
  2. Пусть переменная p изначально равна двум — первому простому числу.
  3. Вычеркнуть из списка все числа от 2p до n, делящиеся на p (то есть, числа 2p, 3p, 4p, …)
  4. Найти первое не вычеркнутое число, большее чем p, и присвоить значению переменной p это число.
  5. Повторять шаги 3 и 4 до тех пор, пока p не станет больше, чем n
  6. Все не вычеркнутые числа в списке — простые числа.

На практике, алгоритм можно немного улучшить следующим образом. На шаге №3, числа можно вычеркивать, начиная сразу с числа p^2, потому что все составные числа меньше его уже будут вычеркнуты к этому времени. И, соответственно, останавливать алгоритм можно, когда p^2 станет больше, чем n.

Ссылки: Править

Эратосфен.

Обнаружено использование расширения AdBlock.


Викия — это свободный ресурс, который существует и развивается за счёт рекламы. Для блокирующих рекламу пользователей мы предоставляем модифицированную версию сайта.

Викия не будет доступна для последующих модификаций. Если вы желаете продолжать работать со страницей, то, пожалуйста, отключите расширение для блокировки рекламы.

Также на ФЭНДОМЕ

Случайная вики