Почему эта реализация Решета Эратосфена неверна?

Цель состоит в том, чтобы найти сумму всех простых чисел до num. Я видел ту же реализацию в другом сообщении, но она также не работает: бесконечный-для-большого-числа">Алгоритм решета Эратосфена в JavaScript, работающий бесконечно для большого числа

Однако решение там тоже неверное, когда я пробую его с 977, оно возвращает 72179, а должно быть 73156.

const sumPrimes = num => {
    var numList = [];
    var output = [];
    for (var i = 0; i < num; i++) {
        numList.push(true);
    }

    for (var i = 2; i <= Math.sqrt(num); i++) {
        if (numList[i]) {
            for (var j = i * i; j < num; j += i) {
                numList[j] = false;
            }
        }
    }

    for (var k = 2; k < num; k++) {
        if (numList[k]) {
            output.push(k);
        }
    }
    var sum = output.reduce((acc, cur) => acc + cur, 0);
    console.log(output);
    return sum;
};

Псевдокод получен из: https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes


person Vincent Chee    schedule 02.09.2017    source источник


Ответы (1)


В вашем коде нет ничего плохого. Он возвращает сумму простых чисел, меньших num, а сумма простых чисел, меньших 977, равна 72179. Ожидаемый ответ 73156 — это сумма простых чисел, меньших или равных 977. Разница составляет 977, потому что 977 — простое число.

person Paul Hankin    schedule 02.09.2017