JavaScript 中的质数

Question

我在 JavaScript 中编写了代码来查找质数。

我创建了一个数组 (var arr) 并将第一个质数放入其中。

我想用存储在数组中的最后一个质数检查 i 值（而不是所有数字更快运行。）

检查我的代码并纠正我的语法。

var arr = [2];
document.getElementById("demo").innerHTML = arr;

function myFunction() {

for (i = 3; i <= 10; i++) {
    if (i % 2 !==0) {
        for (j = 0; j <= arr.length - 1; j++){
            if (i % arr[j] !== 0) {
                arr.push(i);
            }
        }
        document.getElementById("demo").innerHTML = arr;    
    }
}

Answer 1

OP 建议的算法可能有问题，即使它在 2 到 10 的有限范围内工作以在更正代码后产生 2,3,5,7 的预期结果。不幸的是，如果数字的范围扩大，那么非质数可能会悄悄进入，如下所示：

var arr = [2];

function myFunction() {

    for (i = 3; i <= 30; i++) {
        if (i % 2 !==0 && i % Math.sqrt(i) !==0) {
            for (j = 0; j <= arr.length - 1; j++){
                if (i % arr[j] !== 0) {
                    arr.push(i);
                }
                break;
            }
        }
    }
    document.getElementById("demo").innerHTML = arr;
}  
myFunction();

<div id="demo"></div>

以下代码可能效率较低，但好处是无论数字范围有多大，它都能正常工作。该解决方案源自从 here and here.

借用和修改的代码

var arr = [2];

function isPrime( n ) {

    
   // eliminate non-integers 
   if (  n != Math.round(n)  ) {
      return false;
   }
   
   // assume n is prime and test if true
   for(var i=2, max=Math.sqrt(n); i <= max; i++) {
       if ( n % i === 0 ) {
           return false;
       }
    }
    return n > 1;
}

function myFunction() {

    for (i = 3; i <= 30; i++) {
      if ( isPrime(i) ) {
          arr.push(i); 
      }// end-if
    }// end-for
    document.getElementById("demo").innerHTML = arr;
}

myFunction();

<div id="demo"></div>

注意，数组最初以质数 2 开始，当代码在指定范围内遇到质数时，它们将被添加到数组中。顺便说一句，您需要一个 ID 为 "demo" 的 HTML DIV 标签才能工作。而且，你只需要在循环处理完成后，将数组赋值给div元素的innerHTML属性一次。最后，您需要调用 myFunction()。

有趣的相关讨论here。

Answer 2

对于极简代码爱好者，

function primes(limit)
{
  var prime=[], i=1
  while (++i < limit+1) prime.reduce((a,c)=>(i%c)*a,1) && prime.push(i)
  prime.unshift(1)
  return prime
}
[1,2,3,5,10,100].forEach(n=>console.log(`primes(${n})=${primes(n)}`))

Answer 3

function primeNumbers(num){
  let primeNum=[2];
  
  for (let i=3;i<=num;i++){
    let notPrime=[];
    for (let j=2;j<i;j++){
      if (i%j===0){
        notPrime.push(i);
      }
      if (notPrime.length===0){
        primeNum.push(i);
      }
    }
  }
  return primeNum;
}
primeNumbers(10);

JavaScript 中的质数

Prime Number in JavaScript

javascript

primes