Как работает решето Эратосфена(алгоритм) в JavaScript?

Question

[Марик Цукор]

var arr = [];

for (var i = 2; i < 100; i++) {arr[i] = true;}

var p = 2;
do {

  for (i = 2 * p; i < 100; i += p) {arr[i] = false;}

  for (i = p + 1; i < 100; i++) {
    if (arr[i]) break;
  }
  p = i;
} while (p * p < 100); // шаг 5

// Вычисление
var sum = 0;
for (i = 0; i < arr.length; i++) {
  if (arr[i]) {sum += i;}
}
alert(sum);

Не совсем понимаю, как работает этот скрипт, в частности, как работает второй цикл for в родительском цикле do, почему нужно использовать break в этом цикле, и почему условие while такое какое оно есть. С суммой как-нибудь разберусь

Answer 1

[Владислав Яндимиркин]

На википедии достаточно неплохо все описано Вики

второй цикл прерывается, чтобы найти первое число у которого значение true (т.е. оно не зачеркнуто), а затем повторять зачеркивать не простые числа
ищем мы пока квардрат последнего найденного незачеркнутого числа меньше 100
а вообще скрипт считает сумму всех простых чисел не превосходящих 100

Comments

[Марик Цукор]

не совсем понятно, почему такая запись имеет смысл
for (i = p + 1; i < 100; i++) {
if (arr[i]) break;
}
ведь, если число true, то цикл прерывается. А оно полюбому true, т.к p + 1 = 2 + 1 = 3, а 3, это true, поскольку всем числам после 2 в самом первом цикле присвоили значение true. Поэтому цикл сразу прерывается на первой итерации. В чем такой "прикол"? и выражение p = i; как вообще работает здесь, оно же каждый раз получает новое значение, а старое забывается

[Владислав Яндимиркин]

"прикол" как вы говорите в том, что нам не нужно его запоминать. Это всего лишь временная переменная, самое главное вычеркнуть из решета, то что не является простым числом.
Не факт, что полюбому true, вы можете отдебажить код, по отдельным циклам, чтобы лучше его понять...

не полюбому true, так если мы начали с 3 и вычеркнули 6, 9, 12...
проверяем 4? она уже false
for (i = p + 1; i < 100; i++) {
if (arr[i]) break;
}

Answer 2

[Stalker_RED]

Решето Эратосфена работает так: https://ru.wikipedia.org/wiki/%D0%A0%D0%B5%D1%88%D...
И его работа не зависит от того, на каком языка вы его пишете.
Первый цикл for-внутри-do-while отмечает как НЕпростые все числа, которые получаются перемножением i и p
Второй цикл for-внутри-do-while проверяет не является ли простым текущее значение i, и если оно простое, завершает свою работу. При этом do-while перезапускается, но уже с новым значением p.
Условие while (p * p < 100) можно оптимизировать так: while (p < 10)

Добавил флуда в консоль, чтоб было понятнее что происходит: https://jsfiddle.net/L1ahatbk/

Comments

[Марик Цукор]

тут написано:
2. Пусть переменная p изначально равна двум — первому простому числу.
3. "Зачеркнуть в списке числа от 2p до n считая шагами по p (это будут числа кратные p: 2p, 3p, 4p, …)."
это означает, что p = 2, а в 3 шаге написано, что зачеркнуты должны четные числа, притом 3p никак не попадает под эту категорию, т.к он не кратен 2. Опечатка? в алгоритме на js совсем другое. В коде видно, что сначала вычеркиваем все кратные, и там нету 3-ойки

[Stalker_RED]

BeriaFantom: В первый проход цикла do-while будут вычеркнуты все четные. Во второй - все кратные трем, в третий - все кратные пяти. (кратные четырем не нужно вычеркивать, т.к. они были кратны двум!). По этой же причине не вычеркивются числа кратные шести и восьми - они ведь и так вычеркнуты!

[Stalker_RED]

BeriaFantom: Вот еще подробнее расписал https://jsfiddle.net/L1ahatbk/1/
смотрите в консоль

[Марик Цукор]

Stalker_RED: в википедии просто написан немного другой алгоритм, поэтому запутался)

[Stalker_RED]

BeriaFantom: В скрипте используется тот-же алгоритм что описан в википедии. Может он немножко оптимизирован, и поэтому не так очевиден.

2-3 недели на алгоритмы - это очень оптимистично, наверное :)
За это время вы немножко ознакомитесь с теорией, и может быть запомните несколько самых известных названий.

Знать алгоритмы и паттерны полезно - можно брать готовые вместо того, чтобы придумывать их самому. Еще полезно понимать алгоритмическую сложность - будет меньше шансов накодить что-то тормозное и зависающее.