javascript - 将所有素数相加达到某个数字

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() 方法不正确。你可以做一些像下面这样的事情。

编辑:正如 @Amadan 所指出的，算法的复杂性从 O(n) 降低到 O(sqrt(n))

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
    }