Project Euler第7题：求第10001个素数代码遇性能问题求助

你的代码逻辑是对的，但isPrime函数的效率过低，导致计算第10001个素数时运行时间太长，被FreeCodeCamp平台判定为潜在无限循环。

问题分析 #

原isPrime函数从2遍历到n-1来判断素数，对于大数（比如接近104743的数），需要执行几十万次循环，叠加到nthPrime的循环里，整体计算量爆炸，远超平台的时间限制。

优化方案 #

针对素数判断做以下优化，能大幅提升效率：

• 只需要遍历到n的平方根：如果n有大于其平方根的因数，必然存在一个对应的小于平方根的因数，没必要遍历到n-1。
• 提前排除偶数：除了2本身，所有偶数都不是素数，直接返回false。
• 遍历奇数：排除偶数后，只需要检查奇数因数，步长设为2。

另外，nthPrime里的数组可以不用存所有素数，直接计数即可，节省内存（可选优化）。

优化后的代码 #

function isPrime(n) {
  if (n <= 1) return false;
  if (n === 2) return true;
  // 排除偶数
  if (n % 2 === 0) return false;
  // 只遍历到平方根，且只检查奇数
  for (let i = 3; i <= Math.sqrt(n); i += 2) {
    if (n % i === 0) {
      return false;
    }
  }
  return true;
}

function nthPrime(n) {
  let primeCount = 0;
  let currentNum = 2;
  while (primeCount < n) {
    if (isPrime(currentNum)) {
      primeCount++;
      // 找到第n个素数时直接返回，不用继续循环
      if (primeCount === n) {
        return currentNum;
      }
    }
    currentNum++;
  }
}

console.log(nthPrime(10001)); // 输出104743

效果说明 #

优化后的isPrime函数循环次数从n-2次降到最多sqrt(n)/2次，计算第10001个素数的速度会提升几个数量级，能在平台限制的时间内完成计算，不会再触发潜在无限循环的提示。

内容的提问来源于stack exchange，提问作者RogerYueh