为什么我的算法在这个数字上失败了

Question

我正在尝试编写一个算法来计算小于或等于给定数字参数的素数之和。这是我的代码：

function sumPrimes(num) {
// populates the array with numbers uptp the given num
let prime = [], i = 2;
while (prime.indexOf(num) < 0){
prime.push(i)
i++;
}
// filters the array leaving only the prime numbers and sums all prime numbers
let result = prime
.filter(function (a){
if(a === 2 ||a === 3 || a === 5 || a === 7){
return a
} else {
return a % 2 > 0 && a % 3 > 0 && a % 5 > 0 && a % 7 > 0
}}).reduce((a,b) => a+b)

console.log(result)
return result
}
sumPrimes(977); //outputs 108789 instead of 73156

我的过滤函数检查一个可同时被2、3、5、7整除的给定数字是否返回大于零的余数，如果这样的数字是素数的话。然而，当提供的自变量为977时，它会崩溃并输出错误的和。有人能弄清楚这里发生了什么吗？

Answer 1

根据我的评论：您对素数的检查是错误的。一个数不能除以2、3、5或7并不意味着它是素数。您可以简单地从这个答案中回收素数检查逻辑：JavaScript中的数字素数测试，并优化循环，使您只执行一次迭代。

从最小素数2开始一个for循环，将其递增，直到达到目标数。在for循环中，如果数字是素数，请检查它：如果是素数，则将其添加到和中。

这种方法的优点是：

1. 您不会在prime数组中存储任意大的素数数组，该数组最终会通过求和来减少。当然，这是在假设你不需要素数的情况下进行的
2. 与旧代码相比，您不需要执行多次迭代，在旧代码中，您可以执行重复迭代：(1(while循环生成2和目标数字之间的所有数字，(2(filter素数检查，以及(3(reduce方法

// Adapted from: https://stackoverflow.com/questions/40200089/number-prime-test-in-javascript
function isPrime(num) {
for (let i = 2, s = Math.sqrt(num); i <= s; i++)
if (num % i === 0) return false;
return num > 1;
}
function sumPrimes(num) {
let sum = 0;

for (let n = 2; n <= num; n++) {
if (isPrime(n)) {
sum += n;
}
}
console.log(sum);
return sum;
}
sumPrimes(977); // Outputs 73156 as expected

Answer 2

要检查一个数字是否是素数，它不应该被任何其他素数整除。所以，虽然你的逻辑是正确的，但你需要不断地扩展你的素数数组。这可以这样实现：

const primeArray = (n) => {
var p = [2];
if (n<2) return [];
if (n===2) return [2];
for (let i=3;i<=n;i+=2) if (p.every(x=>i%x)) p.push(i);
return p;
}

我们从第一个素数开始，然后每隔一秒检查从3开始的数字，因为所有偶数都可以被2整除。在迭代i+2时，我们只需检查i是否可以被任何已经确定的素数整除。如果不是这种情况(i%x(，我们将素数数组扩展i。

Answer 3

这里是另一个可扩展的最低限度和性能优化版本的Erastostence筛，带有一个只用于测试当前数字平方根的盖子：

function primeArr(n){
for (var primes=[],i=1,j=0,cap=2; ++i<=n;){
if (i>2 && i==cap) cap=primes[j]*primes[j++];
if (primes.slice(0,j-1).every(p=>i%p)) primes.push(i)
}
return primes;
}
let pa=primeArr(977);
console.log("sum:", pa.reduce((a,c)=>a+=c));
console.log("all primes:", pa.join(" "));

Answer 4

通过prime lib:实现完整快速的解决方案

import {generatePrimes, stopOnValue} from 'prime-lib';
const i = stopOnValue(generatePrimes(), 977);
let sum = 0;
for (let a of i) {
sum += a;
}
console.log(sum); //=> 73156