Сложение всех простых чисел до определенного числа

Question

Я должен написать алгоритм, который возвращает сумму всех простых чисел до определенного числа (аргумент), включая сам аргумент.Этот код, кажется, работает очень хорошо (я тестировал его на меньших числах), однако должна быть ошибка, потому что, когда я передаю 977 в качестве аргумента, программы возвращают 108789 , чтопредположительно не правильно.Согласно freecodecamp.org, он должен вернуть 73156 .Я уже проверил массив перед добавлением значений, но я не вижу проблемы здесь.

function sumPrimes(num) {
  function isPrime(n){
   return ((n/2 === 1 || n/3 === 1 || n/5 === 1 || n/7 === 1)?true: 
     (n%2===0 || n%3 === 0 || n%5 ===0 || n%7 === 0)? 
     false:true);
  };

  let result = [];
  let final;

  for(let i = 2; i <= num; i++){
    if(isPrime(i)){
      result.push(i);
    }
  }

  final = result.reduce((x,y) => x + y);

  console.log(final); // returns 108789

}

sumPrimes(977);

Answer 1

Ваш метод isPrime () неверен.Вместо этого вы можете сделать что-то вроде ниже.

Редактировать: Сложность алгоритма уменьшена с O (n) до O (sqrt (n)), как указано @ Amadan

function sumPrimes(num) {

      function isPrime(n){
           for(let i = 2, k = Math.sqrt(n); i <= k; i++)
              if(n % i === 0) 
                 return false; 
           return true;
      };

      let result = [];
      let final;

      for(let i = 2; i <= num; i++){
        if(isPrime(i)){
          result.push(i);
        }
      }

      final = result.reduce((x,y) => x + y); 
      console.log(final); // returns 73156
    }

Answer 2

Ваш isPrime совершенно не прав.Прежде всего, вы проверяете делимость только на первые четыре простых числа;Вы должны проверить делимость на все простые числа до квадратного корня от числа, которое вы проверяете, чтобы быть уверенным.(Вы также можете проверить с не простыми числами, если вы не хотите беспокоиться о сортировке простых чисел из не простых чисел на этом этапе.) Во-вторых, независимо от того, равен остаток 1 или нет, разница не существует - он только между 0а не 0, что важно.

Алгоритмы тестирования простоты очень хорошо известны и описаны во всем Интернете;для начала взгляните на Википедию по простым числам для обзора и здесь для конкретного алгоритма, который, я предполагаю, вы использовали, хотя для вашего конкретного варианта использования (сумма всех простых чисел)меньше чем N), Сито Эратосфена должно быть намного лучше.

Answer 3

Используемый вами метод неверен, так как он проверяет только определенное количество значений, что было бы проблематично для больших чисел.

Как упомянуто в одном из ответов выше, циклический просмотр всех чисел до получения квадратного корня из этого числа также является допустимым методом, однако есть еще более быстрый и более эффективный метод, называемый Сито Эратосфена.

Этот метод работает с удалением результатов, которые мы уже знаем как ложные, а не вычисляя их.

Вы можете прочитать об этом подробнее здесь - Сито Эратосфена

Answer 4

Ваша основная функция не работает должным образом, вы можете прочитать этот пост о создании. Однако остальная часть вашей функции работает, как и ожидалось.

Answer 5

Ваша функция isPrime () неверна.Если вы хотите обрабатывать что-либо, кроме простых мелких простых чисел, вы не можете просто жестко закодировать простые числа для проверки.Например, isPrime (143) вернет true, но 143 = 11 * 13, поэтому не является простым.