0

我试图找到第 10,001 个素数。我看过其他人写的代码，但我不太明白它的意思。我用 JavaScript 编写了一些代码，在其中尝试使用 Eratosthenes 筛。我不确定问题是什么。看起来它应该可以正常工作，但我得到了错误的答案。

var compute = function() {
var prime = [2,3,5,7,11,13,17,19];
for(var i=20; i<=80000;i++) {
if(i%2!==0 && i%3!==0 && i%5!==0 && i%7!==0 && i%11!==0 && i%13!==0 && i%17!==0 &&      i%19!==0) {
 prime.push(i);
  }
 }  
 console.log(prime[10000]);
};

 compute();
4

2 回答 2

3

这是一个简单的方法，但要找到百万分之一

（在某些机器中甚至是千分之一）

你需要用超时把它切碎，

或将其发送给网络工作者以防止锁定。

你只需要检查主要除数，当你收集它们时，

因为每个数字都是素数的乘积

或者本身就是素数。

function nthPrime(nth){
    var P= [2], n= 3, div, i, limit,isPrime;
    while(P.length<nth){
        div= 3, i= 1;
        limit= Math.sqrt(n)+1;
        isPrime= true;
        while(div<limit){
            if(n%div=== 0){
                isPrime= false;
                div= limit;
            }
            else div= P[i++] || div+ 2;
        }
        if(isPrime) P.push(n);
        n+= 2;
    }
    return P[P.length-1];
}

警报（nthPrime（10001））；

于 2013-04-18T04:28:50.003 回答
2

您的代码没有实现 Eratosthenes 的筛子。您必须执行以下步骤（来源：http ://en.wikipedia.org/wiki/Sieve_of_Eratosthenes ）：

  1. 创建一个从 2 到 n 的连续整数列表：(2, 3, 4, ..., n)。
  2. 最初，让 p 等于 2，即第一个素数。
  3. 从 p 开始，以 p 为增量向上计数，并在列表中标记每个大于 p 本身的数字。这些将是 p 的倍数：2p、3p、4p 等；请注意，其中一些可能已经被标记。
  4. 在未标记的列表中找到第一个大于 p 的数字。如果没有这样的号码，请停止。否则，现在让 p 等于这个数（即下一个素数），然后从步骤 3 开始重复。

如果要找到第 10001 个素数，则必须选择足够大的 n，以使生成的数组至少包含 10001 个元素，然后选择第 10001 个元素作为结果。

于 2013-04-18T04:17:07.643 回答