Javascript 如何找到0-100之间的素数？

How to find prime numbers between 0 - 100?

提问by user1599757

In Javascript how would i find prime numbers between 0 - 100? i have thought about it, and i am not sure how to find them. i thought about doing x % x but i found the obvious problem with that. this is what i have so far: but unfortunately it is the worst code ever.

在 Javascript 中，我如何找到 0 - 100 之间的素数？我已经考虑过了，我不知道如何找到它们。我想过做 x % x 但我发现了明显的问题。这是我到目前为止所拥有的：但不幸的是，这是有史以来最糟糕的代码。

var prime = function (){
var num;
for (num = 0; num < 101; num++){
    if (num % 2 === 0){
        break;
    }
    else if (num % 3 === 0){
        break;
    }
    else if (num % 4=== 0){
        break;
    }
    else if (num % 5 === 0){
        break;
    }
    else if (num % 6 === 0){
        break;
    }
    else if (num % 7 === 0){
        break;
    }
    else if (num % 8 === 0){
        break;
    }
    else if (num % 9 === 0){
        break;
    }
    else if (num % 10 === 0){
        break;
    }
    else if (num % 11 === 0){
        break;
    }
    else if (num % 12 === 0){
        break;
    }
    else {
        return num;
    }
}
};
console.log(prime());

回答by Ted Hopp

Here's an example of a sieve implementation in JavaScript:

下面是 JavaScript 中筛选实现的示例：

function getPrimes(max) {
    var sieve = [], i, j, primes = [];
    for (i = 2; i <= max; ++i) {
        if (!sieve[i]) {
            // i has not been marked -- it is prime
            primes.push(i);
            for (j = i << 1; j <= max; j += i) {
                sieve[j] = true;
            }
        }
    }
    return primes;
}

Then getPrimes(100)will return an array of all primes between 2 and 100 (inclusive). Of course, due to memory constraints, you can't use this with large arguments.

然后getPrimes(100)将返回一个包含 2 到 100（含）之间的所有素数的数组。当然，由于内存限制，您不能将其用于大参数。

A Java implementation would look very similar.

Java 实现看起来非常相似。

回答by DavidS

Here's how I solved it. Rewrote it from Java to JavaScript, so excuse me if there's a syntax error.

这是我解决它的方法。把它从 Java 改写成 JavaScript，所以如果有语法错误，请见谅。

function isPrime (n)
{
    if (n < 2) return false;

    /**
     * An integer is prime if it is not divisible by any prime less than or equal to its square root
     **/

    var q = Math.floor(Math.sqrt(n));

    for (var i = 2; i <= q; i++)
    {
        if (n % i == 0)
        {
            return false;
        }
    }

    return true;
}

A number, n, is a prime if it isn't divisible by any other number other than by 1 and itself. Also, it's sufficient to check the numbers [2, sqrt(n)].

如果一个数 ,n不能被除 1 和它本身以外的任何其他数整除，则它是素数。此外，检查数字 [2, sqrt(n)] 就足够了。

回答by Evan Kennedy

Here is the live demo of this script: http://jsfiddle.net/K2QJp/

这是这个脚本的现场演示：http: //jsfiddle.net/K2QJp/

First, make a function that will test if a single number is prime or not. If you want to extend the Number object you may, but I decided to just keep the code as simple as possible.

首先，创建一个函数来测试单个数字是否为素数。如果你想扩展 Number 对象，你可以，但我决定让代码尽可能简单。

function isPrime(num) {
    if(num < 2) return false;
    for (var i = 2; i < num; i++) {
        if(num%i==0)
            return false;
    }
    return true;
}

This script goes through every number between 2 and 1 less than the number and tests if there is any number in which there is no remainder if you divide the number by the increment. If there is any without a remainder, it is not prime. If the number is less than 2, it is not prime. Otherwise, it is prime.

此脚本遍历小于该数字的 2 到 1 之间的每个数字，并测试是否有任何数字在将数字除以增量时没有余数。如果有任何没有余数，它不是质数。如果数字小于 2，则它不是质数。否则，它是主要的。

Then make a for loop to loop through the numbers 0 to 100 and test each number with that function. If it is prime, output the number to the log.

然后使用 for 循环遍历数字 0 到 100 并使用该函数测试每个数字。如果是质数，则将数字输出到日志中。

for(var i = 0; i < 100; i++){
    if(isPrime(i)) console.log(i);
}

回答by Luchian Grigore

Whatever the language, one of the best and most accessible ways of finding primes within a range is using a sieve.

无论使用什么语言，在一个范围内寻找素数的最好和最容易获得的方法之一就是使用筛分。

Not going to give you code, but this is a good starting point.

不会给你代码，但这是一个很好的起点。

For a small range, such as yours, the most efficient would be pre-computing the numbers.

对于像您这样的小范围，最有效的方法是预先计算数字。

回答by Redu

I have slightly modified the Sieve of Sundaramalgorithm to cut the unnecessary iterations and it seems to be very fast.

我稍微修改了Sieve of Sundaram算法以减少不必要的迭代，它似乎非常快。

This algorithm is actually two times faster than the most accepted @Ted Hopp's solutionunder this topic. Solving the 78498 primes between 0 - 1M takes like 20~25 msec in Chrome 55 and < 90 msec in FF 50.1. Also @vitaly-t's get next prime algorithmlooks interesting but also results much slower.

这个算法实际上比这个主题下最被接受的@Ted Hopp 的解决方案快两倍。解决 0 - 1M 之间的 78498 个质数在 Chrome 55 中需要 20~25 毫秒，在 FF 50.1 中需要 < 90 毫秒。另外@vitaly-t 的 get next prime 算法看起来很有趣，但结果也慢得多。

This is the core algorithm. One could apply segmentation and threading to get superb results.

这是核心算法。人们可以应用分段和线程来获得极好的结果。

"use strict";
function primeSieve(n){
  var a = Array(n = n/2),
      t = (Math.sqrt(4+8*n)-2)/4,
      u = 0,
      r = [];
  for(var i = 1; i <= t; i++){
    u = (n-i)/(1+2*i);
    for(var j = i; j <= u; j++) a[i + j + 2*i*j] = true;
  }
  for(var i = 0; i<= n; i++) !a[i] && r.push(i*2+1);
  return r;
}

var primes = [];
console.time("primes");
primes = primeSieve(1000000);
console.timeEnd("primes");
console.log(primes.length);

The loop limits explained:

循环限制解释：

Just like the Sieve of Erasthotenes, the Sieve of Sundaram algorithm also crosses out some selected integers from the list. To select which integers to cross out the rule is i + j + 2ij ≤ n where i and j are two indices and n is the number of the total elements. Once we cross out every i + j + 2ij, the remaining numbers are doubled and oddified (2n+1) to reveal a list of prime numbers. The final stage is in fact the auto discounting of the even numbers. It's proof is beautifully explained here.

就像 Erasthotenes 的筛选一样，Sundaram 的筛选算法也会从列表中划掉一些选定的整数。要选择要划掉的整数，规则是 i + j + 2ij ≤ n，其中 i 和 j 是两个索引，n 是总元素的数量。一旦我们划掉每一个 i + j + 2ij，剩下的数字就会被加倍和奇数化 (2n+1) 以显示素数列表。最后阶段实际上是偶数的自动折扣。它的证明在这里得到了很好的解释。

Sieve of Sundaram is only fast if the loop indices start and end limits are correctly selected such that there shall be no (or minimal) redundant (multiple) elimination of the non-primes. As we need i and j values to calculate the numbers to cross out, i + j + 2ij up to n let's see how we can approach.

Sundaram 的筛选只有在正确选择循环索引开始和结束限制的情况下才能快速进行，这样就不会（或最少）消除（或最小）非素数的冗余（多重）消除。由于我们需要 i 和 j 值来计算要划掉的数字，因此 i + j + 2ij 到 n 让我们看看如何处理。

i)So we have to find the the max value i and j can take when they are equal. Which is 2i + 2i^2 = n. We can easily solve the positive value for i by using the quadratic formula and that is the line with t = (Math.sqrt(4+8*n)-2)/4,

i)所以我们必须找到 i 和 j 相等时可以取的最大值。即 2i + 2i^2 = n。我们可以使用二次公式轻松求解 i 的正值，即t = (Math.sqrt(4+8*n)-2)/4,

j)The inner loop index j should start from i and run up to the point it can go with the current i value. No more than that. Since we know that i + j + 2ij = n, this can easily be calculated as u = (n-i)/(1+2*i);

j)内循环索引 j 应该从 i 开始并运行到它可以与当前 i 值一致的点。仅此而已。由于我们知道 i + j + 2ij = n，这可以很容易地计算为u = (n-i)/(1+2*i);

While this will not completely remove the redundant crossings it will "greatly" eliminate the redundancy. For instance for n = 50 (to check for primes up to 100) instead of doing 50 x 50 = 2500, we will do only 30 iterations in total. So clearly, this algorithm shouldn't be considered as an O(n^2) time complexity one.

虽然这不会完全消除冗余交叉，但它会“极大地”消除冗余。例如，对于 n = 50（检查最多 100 的素数）而不是 50 x 50 = 2500，我们总共将只进行 30 次迭代。很明显，这个算法不应该被视为 O(n^2) 时间复杂度的算法。

i  j  v
1  1  4
1  2  7
1  3 10
1  4 13
1  5 16
1  6 19
1  7 22  <<
1  8 25
1  9 28
1 10 31  <<
1 11 34
1 12 37  <<
1 13 40  <<
1 14 43
1 15 46
1 16 49  <<
2  2 12
2  3 17
2  4 22  << dupe #1
2  5 27
2  6 32
2  7 37  << dupe #2
2  8 42
2  9 47
3  3 24
3  4 31  << dupe #3
3  5 38
3  6 45
4  4 40  << dupe #4
4  5 49  << dupe #5

among which there are only 5 duplicates. 22, 31, 37, 40, 49. The redundancy is around 20% for n = 100 however it increases to ~300% for n = 10M. Which means a further optimization of SoS bears the potentital to obtain the results even faster as n grows. So one idea might be segmentation and to keep n small all the time.

其中只有5个重复。22、31、37、40、49。对于 n = 100，冗余度约为 20%，但对于 n = 10M，它增加到 ~300%。这意味着进一步优化 SoS 有可能随着 n 的增长更快地获得结果。因此，一个想法可能是分段并始终保持 n 小。

So OK.. I have decided to take this quest a little further.

所以好吧..我决定更进一步地进行这个任务。

After some careful examination of the repeated crossings I have come to the awareness of the fact that, by the exception of i === 1case, if either one or both of the ior jindex value is among 4,7,10,13,16,19... series, a duplicate crossing is generated. Then allowing the inner loop to turn only when i%3-1 !== 0, a further cut down like 35-40% from the total number of the loops is achieved. So for instance for 1M integers the nested loop's total turn count dropped to like 1M from 1.4M. Wow..! We are talking almost O(n) here.

经过对重复交叉的一些仔细检查后，我意识到一个事实，除了i === 1情况，如果i或j指数值中的一个或两个在 4,7,10,13,16,19.. . 系列，生成重复的交叉。然后仅在 时才允许内循环转动i%3-1 !== 0，从而进一步减少了循环总数的 35-40%。因此，例如对于 1M 整数，嵌套循环的总轮数从 1.4M 下降到 1M。哇..！我们在这里谈论的几乎是 O(n)。

I have just made a test. In JS, just an empty loop counting up to 1B takes like 4000ms. In the below modified algorithm, finding the primes up to 100M takes the same amount of time.

我刚刚做了一个测试。在 JS 中，仅仅一个计数到 1B 的空循环就需要 4000 毫秒。在下面修改后的算法中，找到最多 100M 的素数需要相同的时间。

I have also implemented the segmentation part of this algorithm to push to the workers. So that we will be able to use multiple threads too. But that code will follow a little later.

我还实现了这个算法的分割部分来推送给工作人员。这样我们也可以使用多个线程。但该代码稍后将遵循。

So let me introduce you the modified Sieve of Sundaram probably at it's best when not segmented. It shall compute the primes between 0-1M in about 15-20ms with Chrome V8 and Edge ChakraCore.

因此，让我向您介绍经过修改的 Sundaram 筛网可能在不分段时最好。它将使用 Chrome V8 和 Edge ChakraCore 在大约 15-20 毫秒内计算 0-1M 之间的素数。

"use strict";
function primeSieve(n){
  var a = Array(n = n/2),
      t = (Math.sqrt(4+8*n)-2)/4,
      u = 0,
      r = [];
  for(var i = 1; i < (n-1)/3; i++) a[1+3*i] = true;
  for(var i = 2; i <= t; i++){
    u = (n-i)/(1+2*i);
    if (i%3-1) for(var j = i; j < u; j++) a[i + j + 2*i*j] = true;
  }
  for(var i = 0; i< n; i++) !a[i] && r.push(i*2+1);
  return r;
}

var primes = [];
console.time("primes");
primes = primeSieve(1000000);
console.timeEnd("primes");
console.log(primes.length);

Well... finally I guess i have implemented a sieve (which is originated from the ingenious Sieve of Sundaram) such that it's the fastest JavaScript sieve that i could have found over the internet, including the "Odds only Sieve of Eratosthenes" or the "Sieve of Atkins". Also this is ready for the web workers, multi-threading.

嗯...最后我想我已经实现了一个筛子（它起源于巧妙的 Sundaram 筛子），它是我可以在互联网上找到的最快的 JavaScript 筛子，包括“Eratosthenes 的 Odds only Sieve”或“阿特金斯筛”。这也是为 web 工作者准备的，多线程。

Think it this way. In this humble AMD PC for a single thread, it takes 3,300 ms for JS just to count up to 10^9 and the following optimized segmented SoS will get me the 50847534 primes up to 10^9 only in 14,000 ms. Which means 4.25 times the operation of just counting. I think it's impressive.

这样想。在这台不起眼的单线程 AMD PC 中，JS 需要 3,300 毫秒才能计算到 10^9，而以下优化的分段 SoS 将仅在 14,000 毫秒内为我提供 50847534 个素数，达到 10^9。这意味着只是计数操作的 4.25 倍。我认为它令人印象深刻。

You can test it for yourself;

你可以自己测试一下；

console.time("tare");
for (var i = 0; i < 1000000000; i++);
console.timeEnd("tare");

And here i introduce you to the segmented Seieve of Sundaram at it's best.

在这里，我向您介绍最好的 Sundaram 分段式 Seieve。

"use strict";
function findPrimes(n){
  
  function primeSieve(g,o,r){
    var t = (Math.sqrt(4+8*(g+o))-2)/4,
        e = 0,
        s = 0;
    
    ar.fill(true);
    if (o) {
      for(var i = Math.ceil((o-1)/3); i < (g+o-1)/3; i++) ar[1+3*i-o] = false;
      for(var i = 2; i < t; i++){
        s = Math.ceil((o-i)/(1+2*i));
        e = (g+o-i)/(1+2*i);
        if (i%3-1) for(var j = s; j < e; j++) ar[i + j + 2*i*j-o] = false;
      }
    } else {
        for(var i = 1; i < (g-1)/3; i++) ar[1+3*i] = false;
        for(var i = 2; i < t; i++){
          e = (g-i)/(1+2*i);
          if (i%3-1) for(var j = i; j < e; j++) ar[i + j + 2*i*j] = false;
        }
      }
    for(var i = 0; i < g; i++) ar[i] && r.push((i+o)*2+1);
    return r;
  }
  
  var cs = n <= 1e6 ? 7500
                    : n <= 1e7 ? 60000
                               : 100000, // chunk size
      cc = ~~(n/cs),                     // chunk count
      xs = n % cs,                       // excess after last chunk
      ar = Array(cs/2),                  // array used as map
  result = [];
  
  for(var i = 0; i < cc; i++) result = primeSieve(cs/2,i*cs/2,result);
  result = xs ? primeSieve(xs/2,cc*cs/2,result) : result;
  result[0] *=2;
  return result;
}


var primes = [];
console.time("primes");
primes = findPrimes(1000000000);
console.timeEnd("primes");
console.log(primes.length);

I am not sure if it gets any better than this. I would love to hear your opinions.

我不确定它是否会比这更好。我很想听听你的意见。

回答by weston

A number is a prime if it is not divisible by other primes lower than the number in question.

如果一个数不能被小于该数的其他素数整除，则该数为素数。

So this builds up a primesarray. Tests each new odd candidate nfor division against existing found primeslower than n. As an optimization it does not consider even numbers and prepends 2as a final step.

所以这建立了一个primes数组。测试每个新的奇数候选n除法与现有发现的primes低于n. 作为优化，它不考虑偶数并2作为最后一步。

var primes = [];
for(var n=3;n<=100;n+=2) {
  if(primes.every(function(prime){return n%prime!=0})) {
    primes.push(n);
  }
}
primes.unshift(2);

回答by Vaibhav

To find prime numbers between 0 to n. You just have to check if a number x is getting divisible by any number between 0 - (square root of x). If we pass n and to find all prime numbers between 0 and n, logic can be implemented as -

求 0 到 n 之间的素数。您只需要检查数字 x 是否可以被 0 -（x 的平方根）之间的任何数字整除。如果我们通过 n 并找到 0 和 n 之间的所有素数，逻辑可以实现为 -

  function findPrimeNums(n)
    { 
       var x= 3,j,i=2,
       primeArr=[2],isPrime;
       for (;x<=n;x+=2){
           j = (int) Math.sqrt (x);
           isPrime = true;
           for (i = 2; i <= j; i++)
           {
                if (x % i == 0){
                    isPrime = false;
                    break;
                }
            }
            if(isPrime){
                primeArr.push(x);
            }

        }   

        return primeArr;
    }

回答by Naftali aka Neal

Using recursion combined with the square root rule from here, checks whether a number is prime or not:

使用递归结合此处的平方根规则，检查数字是否为素数：

function isPrime(num){

    // An integer is prime if it is not divisible by any prime less than or equal to its square root
    var squareRoot = parseInt(Math.sqrt(num));
    var primeCountUp = function(divisor){
        if(divisor > squareRoot) {
            // got to a point where the divisor is greater than 
            // the square root, therefore it is prime
            return true;
        }
        else if(num % divisor === 0) {
            // found a result that divides evenly, NOT prime
            return false;
        }
        else {
            // keep counting
            return primeCountUp(++divisor);
        }
    };

    // start @ 2 because everything is divisible by 1
    return primeCountUp(2);

}

回答by Stephen C

Luchian's answer gives you a link to the standard technique for finding primes.

Luchian 的回答为您提供了寻找素数的标准技术的链接。

A less efficient, but simpler approach is to turn your existing code into a nested loop. Observe that you are dividing by 2,3,4,5,6 and so on ... and turn that into a loop.

一种效率较低但更简单的方法是将现有代码转换为嵌套循环。观察你正在除以 2、3、4、5、6 等等……然后把它变成一个循环。

Given that this is homework, and given that the aim of the homework is to help you learn basic programming, a solution that is simple, correct but somewhat inefficient should be fine.

鉴于这是作业，而且作业的目的是帮助您学习基本的编程，一个简单、正确但效率稍低的解决方案应该没问题。

回答by vitaly-t

Here's the fastest way to calculate primes in JavaScript, based on the previous prime value.

这是在 JavaScript 中计算素数的最快方法，基于之前的素数。

function nextPrime(value) {
    if (value > 2) {
        var i, q;
        do {
            i = 3;
            value += 2;
            q = Math.floor(Math.sqrt(value));
            while (i <= q && value % i) {
                i += 2;
            }
        } while (i <= q);
        return value;
    }
    return value === 2 ? 3 : 2;
}

Test

测试

var value = 0, result = [];
for (var i = 0; i < 10; i++) {
    value = nextPrime(value);
    result.push(value);
}
console.log("Primes:", result);

Output

输出

Primes: [ 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 ]

It is faster than other alternatives published here, because:

它比此处发布的其他替代方案更快，因为：

• It aligns the loop limit to an integer, which works way faster;
• It uses a shorter iteration loop, skipping even numbers.

• 它将循环限制与整数对齐，这样工作得更快；
• 它使用较短的迭代循环，跳过偶数。

It can give you the first 100,000 primes in about 130ms, or the first 1m primes in about 4 seconds.

它可以在大约 130 毫秒内为您提供前 100,000 个素数，或在大约 4 秒内提供前 1m 个素数。

 function nextPrime(value) {
        if (value > 2) {
            var i, q;
            do {
                i = 3;
                value += 2;
                q = Math.floor(Math.sqrt(value));
                while (i <= q && value % i) {
                    i += 2;
                }
            } while (i <= q);
            return value;
        }
        return value === 2 ? 3 : 2;
    }

    var value, result = [];
    for (var i = 0; i < 10; i++) {
        value = nextPrime(value);
        result.push(value);
    }

    display("Primes: " + result.join(', '));

    function display(msg) {
        document.body.insertAdjacentHTML(
            "beforeend",
            "<p>" + msg + "</p>"
        );
    }