2

Вот код для поиска всех простых чисел до 100 и выведения их суммы.

Объясните, пожалуйста, каким образом числа от 2 до 100 записываются в массив, а также, куда идет число p?

var arr = [];

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

var p = 2;

do {
  // шаг 3
  for (i = 2 * p; i < 100; i += p) {
    arr[i] = false;
  }

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

  p = i;
} while (p * p < 100); // шаг 5

// шаг 6 (готово)
// посчитать сумму
var sum = 0;
for (i = 0; i < arr.length; i++) {
  if (arr[i]) {
    sum += i;
  }
}

alert( sum );
2

3 ответа 3

7

Объясните, пожалуйста каким образом числа от 2 до 100 записываются в массив,

Используется массив boolean, в котором (после окончания работы алгоритма) i-й элемент равен true тогда и только тогда, когда число i – простое.

а также куда идет число p?

В нем хранится последнее найденное простое число. Когда мы его находим, то вычеркиваем из массива все числа, кратные p, то есть p, 2p, 3p...

Обратите внимание на связанный вопрос об оптимизации этого алгоритма для больших N: Как запилить решето эратосфена для 10^9 ? или хотя бы для 10^8

введите сюда описание изображения

Изображение: Wikipedia, лицензия GNU Free Documentation License. Спасибо jfs за ссылку

2

Судя по коду числа в массив не записываются, в массив записываются флаги. Сначала

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

все элементы массива со 2го по 100й помечаются истиной. Потом в двойном цикле

do {
  // шаг 3
  for (i = 2 * p; i < 100; i += p) {
    arr[i] = false;
  }
...

вычеркиваются кратные.

И в конце уже элементы массива используются в условие при подсчете

  if (arr[i]) {
      sum += i;
  }
1

Чтобы получить Решето Эратосфена до 100, достаточно вычеркнуть простые делители <10: 2,3,5,7 (как показал Nick Volynkin). А если нужно что-то помасштабней, то Вам сюда

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.