Как сделать алгоритм для вычисления суммы простых чисел по принципу Сита Эрастофена?

Question

[Quintis]

Доброго времени суток. Написал код что вычисляет суму простых чисел от нуля до заданого числа. Но все работает нормально при малых числах , когда задаю число 977 должно быть 73156 а у меня 108618.Кто может помочь?

function sumPrimes(num) {
  let numArr = [2];
  let delLength3 = [];
  let delLength5 = [];
  let delLength7 = [];
  for (let i = 4; i <= num; i = i + 3) {
    delLength3.push(i);
  }

  for (let i = 5; i <= num; i = i + 5) {
    delLength5.push(i);
  }

  for (let i = 14; i <= num; i = i + 7) {
    delLength7.push(i);
  }

  for (let i = 2; i <= num; i++) {
    if (i % 2 !== 0) {
      numArr.push(i);
    }
  }

  delLength3.map(el => {
    numArr[el] = "x";
  });

  delLength5.map(el => {
    numArr[el] = "x";
  });

  delLength7.map(el => {
  console.log(el)
  let index = numArr.indexOf(el)
  if (index >= 0) {
    numArr[index] = 'x'
  }
  });

  let newArr = numArr.filter(el => {
    if (typeof el === "number") {
      return el;
    }
  });

  let sumArr = newArr.reduce((a, b) => {
    return a + b;
  });

  console.log(sumArr);
  return sumArr;
}

sumPrimes(977);

ссылка на код https://codesandbox.io/s/adoring-wildflower-c0rf0

Comments

[Lynn «Кофеман»]

Внимательно читать лень, но судя по коду вы считаете простыми все числа которые не делятся на 3, 5 и 7. Например 121.

Было бы смешно, если бы не было так грустно

Answer 1

[Дмитрий]

Много вопросов по коду

1) Почему тут начиная с 4, а не с 3?
for (let i = 4; i <= num; i = i + 3) {

2) Почему тут начиная с 14, а не с 7
for (let i = 14; i <= num; i = i + 7) {

3) Во-первых двойка в массиве у вас уже есть, во вторых зачем условие если можно просто i+=2?

for (let i = 2; i <= num; i++) {
    if (i % 2 !== 0) {
      numArr.push(i);
    }
  }

4) Где прочие простые числа? 11, 13 и т.д.?

Вобщем не видно чтобы этот код мог быть рабочим

Простой и эффективный код для этого случая будет таким

const simpleNumbersSum = max => {
   const arr = new Array(max + 1)
   let sum = 1 + 2; //Или просто 2, если единицу не учитываем
   for (let i = 3; i <= max; i+=2) {
      if (!arr[i]) {
         sum+=i;
         for (let j = i * i; j <= max; j+=i*2) {
            arr[j] = true;
         }
      }
   }
   
   return sum
}

console.log(simpleNumbersSum(977))

Comments

[Quintis]

!arr[i]

а что этот код делает ?

[Дмитрий]

Quintis, Проверяет что это число не было ранее помечено как непростое строкой
arr[j] = true;