将所有质数相加到一定数量

Question

我应该写一个算法，returns 所有素数的总和达到一定数量（参数），包括参数本身。这段代码似乎工作得很好（我在较小的数字上测试过），但是肯定有一个错误，因为当我将 977 作为参数传递时，程序 returns 108789，这应该是不正确的。根据freecodecamp.org，应该是return73156。我已经在添加值之前检查了数组，但我看不到这里的问题。

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完全错了。首先，您只检查前四个质数的可除性；您应该检查所有素数的可除性，直到您要测试的数字的平方根为止。（如果你不想在此时从 non-prime 中排序素数，你也可以用 non-prime 数字进行测试。）其次，余数是否为 1 没有区别- 只有 0 和 0 之间才是重要的。

用于素数测试的算法非常well-known并且在整个 Web 上都有描述；首先，看看 prime numbers for overview, and here for the specific algorithm I assume you were going for, though for your specific use case (sum of all primes less than N), the Sieve of Eratosthenes 上的维基百科应该会好得多。

Answer 2

您的 isPrime() 函数不正确。如果你想处理任何超出普通小素数的事情，你不能简单地硬编码素数来检查。例如 isPrime(143) 将 return 为真，但是 143 = 11*13 所以不是素数。

Answer 3

您的 prime 函数无法正常工作，您可能需要阅读关于构建一个的内容。但是，您的其余功能似乎按预期运行。

Answer 4

您的 isPrime() 方法不正确。您可以改为执行以下操作。

编辑：正如

所指出的那样，算法的复杂度从 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
    }

Answer 5

您使用的方法是错误的，因为它只检查一定数量的值，这对于大量值来说会有问题。

如上面的一个答案所述，遍历所有数字直到该数字的平方根也是一种有效的方法，但是有一种更快、更有效的方法叫做埃拉托色尼筛法。

此方法用于删除我们已知为错误的结果而不是对其进行计算。

您可以在这里阅读更多内容 - Sieve of Eratosthenes

将所有质数相加到一定数量

Adding up all the primes up to a certain number

javascript

primes