获取前N个质数之和javascript

Question

我正在尝试找到前 N 个素数的总和，下面附上了我的代码。我正在为最后一部分而苦苦挣扎（求和）。至此我已经定义了什么是素数，并且得到了前N个素数

function isPrime(number) {
  if (number <= 1) return false;
  if (number === 2) return true;
  else {
    for (let i = 2; i < number; i++) {
      if (number % i === 0) return false;
    }
    return true;
  }
}
console.log(isPrime(6)); //false 

function getNprimes(n) {
  const arr = [];
  let i = 2

  while (arr.length < n) {
    if (isPrime(i)) {
      arr.push(i)
    }
    i++
  }
  return arr;
}
console.log(getNprimes(5)); //[2, 3, 5, 7, 11]

const sumOfNPrimes = (num) => {
  let sum = getNprimes(num);
  if (sum === 0) {
    sum = getNprimes(num + 1)
    return sum;
  }
}
console.log(sumOfNPrimes(4));

Answer 1

检查 sum === 0 将始终 return false 因为 sum 是一个数组并且您使用的是严格相等性检查类型。您应该改为检查 length 属性，并使用 != 运算符（例如，仅当数组的长度不是 0 时才执行代码）。

要计算结果数组的总和，可以使用Array#reduce:

function isPrime(number) {
  if (number <= 1) return false;
  if (number === 2) return true;
  else {
    for (let i = 2; i < number; i++) {
      if (number % i === 0) return false;
    }
    return true;
  }
}
console.log(isPrime(6)); //false 

function getNprimes(n) {
  const arr = [];
  let i = 2

  while (arr.length < n) {
    if (isPrime(i)) {
      arr.push(i)
    }
    i++
  }
  return arr;
}
console.log(getNprimes(5)); //[2, 3, 5, 7, 11]

const sumOfNPrimes = (num) => {
  let sum = getNprimes(num).reduce((a, b) => a + b);
  return sum
}
console.log(sumOfNPrimes(4));

Answer 2

您实现的算法将在 O(N sqrt(N)) 中运行并且它正在为每个查询找到总和。因此，如果您想降低代码的时间复杂度，那么您可以在 O(N log (log N)) 中实现运行s 的 erastosthenes 筛法，并将素数之和的值存储在 O(N ) 然后以 O(1) 时间复杂度回答所有查询。下面是这个想法在javascript中的实现：

let primes = [];
let primeSum = [2];
const N = 1000001;

function generatePrimes(){
    let isPrime = [];
    for(let i=1; i<N; i++) isPrime.push(true);
    for(let i=2; i<N; i++){
        if(!isPrime[i]) continue; // if number is not prime
        primes.push(i); // add prime number
        for(let j=2*i; j<N; j += i){
            isPrime[j] = false; // marking all multiples of                  current prime as non prime
        }
    }

// calculate prime sums from 0 index to ith index
    for(let i=1; i<primes.length; i++){
        if(i < 10) console.log(primes[i]);
        primeSum.push(Number(Number(primes[i])+Number(primeSum[i-    1])));
    }
}

generatePrimes();

// answer query in O(1) for n = 10:
const n = 3;
console.log(primeSum[n-1]);

您也可以使用此代码回答 l 到 r 范围查询质数和

ps：抱歉英语不好

获取前N个质数之和javascript

Get the sum of first N primes javascript

javascript

arrays

sum