找出前100个素数

Finding the first 100 prime numbers

本文关键字：100个      更新时间：2023-09-26

我正在查找前100个素数。不是1-100的素数。我需要一些关于这个代码的帮助。

    var p = function(n){
    var x = Math.sqrt(n);
    if(n==2){return 2;}
    else if (n % 2===0){return 0;}
    var i=3;
    for(i=3; i < x; i+=2){
            if(n%i===0){return 0;}
    }
    return n;
};

var firstKPrime = function(k){
        var i=1;
        var arr =[];
        for(i = 1; i < k+1; i++){
                if(i==2){arr.push(p(i));}
                if(i>2 && i%2!==0){
                        if (p(i)>1){arr.push(p(i));}}
                    }
                return arr;
            };
                var fmt = function(arr){
                    return arr.join(",");
            };
            var k = 100;
            console.log("firstKPrime(" + k + ")");
            console.log(fmt(firstKPrime(k)));

我不想让它找到1-100的素数来帮助我修改这个

var first100primes = [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,271,277,281,283,293,307,311,313,317,331,337,347,349,353,359,367,373,379,383,389,397,401,409,419,421,431,433,439,443,449,457,461,463,467,479,487,491,499,503,509,521,523,541];

呵呵。。。

不过，严肃地说，你应该遵循以下模式：

  • 创建一个数组primes和一个整数i=1
  • 在primes.length < 100期间，请执行以下操作：
    • 增量i
    • 对于2和sqrt(i)之间的所有整数j：
      • 如果i % j == 0，则继续顶部循环
    • 如果你达到这个点，那么它就是一个素数，所以把i推到primes上

上面的示例实现：

(function() {
    var primes = [2];
    window.getNprimes = function(n) {
        var i = primes.length == 1 ? 1 : primes[primes.length-1], j, l;
        main:
        while((l=primes.length) < n) {
            i += 2;
            for( j=0; j<l; j++) {
                if( i % primes[j] == 0) continue main;
            }
            primes.push(i);
        }
        return primes.slice(0,n);
    };
})();

这是我能想到的最佳结果，特别是如果你多次调用getNprimes(100)，它只会在第一次计算它，下次只返回相同的结果。

如果你不介意使用Lazy.js这样的库，那么你可以简单地这样做：

var first100primes = Lazy
    .generate(infiniteSequence(2))
    .filter(isPrime)
    .take(100)
    .toArray();
function infiniteSequence(start, step) {
    if (typeof start === "undefined") start = 0;
    if (typeof step === "undefined") step = 1;
    return function (i) {
        return start + i * step;
    };
}
function isPrime(n) {
    var sqrtn = Math.sqrt(n);
    for (var i = 2; i <= sqrtn; i++)
        if (n % i === 0) return false;
    return true;
}

仅此而已。如果你不想使用Lazy.js，那么你可以这样做：

var first100primes = [], n = 2;
do if (isPrime(n++)) first100primes.push(n - 1);
while (first100primes.length < 100);
function isPrime(n) {
    var sqrtn = Math.sqrt(n);
    for (var i = 2; i <= sqrtn; i++)
        if (n % i === 0) return false;
    return true;
}

查看演示：http://jsfiddle.net/a3mKv/

而不是使用for（i=1；i<k+1；i++）
使用

j = 1;
i=2;
while(j <= k)
{
  if(i==2){arr.push(p(i));}
                if(i>2 && i%2!==0)
                {
                        if (p(i)>1)
                        {arr.push(p(i));j++;}
                }
  i++;
}

我会使用arr.length属性来查看已经找到了多少素数，并将其与参数k进行比较。

大致如下：

var firstKPrime = function(k){
var i=1;
var arr =[];
while (arr.length < k)
{
    if(i == 2)
    { 
        arr.push(p(i)); 
    }
    if(i>2 && i%2!==0)
    {
        if (p(i)>1)
        {
            arr.push(p(i));
        }
    }
    i++;
}
return arr;
};
相关文章：