Мастер-классы по Javascript Екатеринбург Ростов-на-Дону Москва Узнать больше...
Содержание (скрыть) Содержание (показать)

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

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

Древний алгоритм «Решето Эратосфена» для поиска всех простых чисел до n выглядит так:

  1. Создать список последовательных чисел от 2 до n: 2, 3, 4, ..., n.
  2. Пусть p=2, это первое простое число.
  3. Зачеркнуть все числа в списке с разницей в p, т.е. 2p, 3p, 4p и т.д. В случае p=2 это будут 2,4,6,8....
  4. Поменять значение p на первое незачеркнутое число после p.
  5. Повторить шаги 3-4 пока p2 < n.
  6. Все оставшиеся незачеркнутыми числа - простые.

Посмотрите также анимацию алгоритма.

Реализуйте «Решето Эратосфена» в JavaScript. Найдите все простые числа до 100 и выведите их сумму.

Решение
Решение

Их сумма равна 1060.

Решение: tutorial/intro/array/sieve.html.

#181
Наверх

Реклама

Нашли опечатку?

Нашли опечатку на сайте? Что-то кажется странным?
Выделите соответствующий текст и нажмите Ctrl+Enter!

Последние Комментарии

Помоги другим!

Помоги другим узнать о хорошей статье!