在JavaScript中检查数字是否为质数

Question

在JavaScript中检查数字是否为质数

let inputValue= 7;
let isprime=inputValue==1? false:true;  //bcoz 1 is not prime

for(let i=2;i<inputValue;i++){
  inputValue%i==0? isprime*=false :isprime*=true;
};

alert(`${inputValue} is ${isprime? 'prime':'not prime'} number`);

- John Ozenua

---

可能是Prime Numbers JavaScript的重复问题。 - nicovank

你的for循环永远不会迭代超过一次。 - Shashwat Kumar

@ShashwatKumar 请解释为什么以及如何修复这个问题。 - John Ozenua

这很低效，不要使用循环来做这样的事情... 查看我的答案，以找到最简单的CPU方式来查找质数... 在这里 - 255.tar.xz

代码流使用了你的代码来推广他们的软件...我觉得这很有趣。 - vik

这里添加了另一个答案 https://dev59.com/O5nga4cB1Zd3GeqPXVub#74855773 - Serkan KONAKCI

Answer 1

时间复杂度： O(sqrt(n))

空间复杂度： O(1)

const isPrime = num => {
    for(let i = 2, s = Math.sqrt(num); i <= s; i++) {
        if(num % i === 0) return false;
    }
    return num > 1;
}

- Ihor Sakailiuk

---

检查等于 4 的目的是什么？也可以只检查奇数。 - zerkms

那就把它改成 i <= s，并移除那个丑陋的硬编码条件吧？ - zerkms

@Saka7的回答非常有帮助，尤其是sqrt优化部分，这是我没有考虑过的。@zerkms建议只检查奇数（当然大于2），这是我预期在优化解决方案时会看到的。这种方法可以极大地优化您的解决方案。我已经创建了这个JSPerf测试 来演示。顺便说一句，感谢你们两个的指导。 - gfullam

isPrime(0) returns true, which is not the case.For the function to be mathematically correct, you need to add another condition to the return statement:return num !== 1 && num !== 0; - pavloko

可以使用条件 return num >= 2;，因为质数必须是大于1的自然数，而不是1或0。这样可以替代原来的语句 return num !== 1 && num !== 0;。 - Angel Cloudwalker

Answer 2

这里有一个小建议，你为什么要运行整个n个数字的循环？

如果一个数是质数，它将有2个因子（1和数字本身）。如果不是质数，它们将有1、数字本身以及更多的因子。你不需要运行循环直到这个数字，也许你可以考虑运行它直到这个数字的平方根。

你可以通过欧拉质数逻辑来执行。查看以下代码片段：

function isPrime(num) {
  var sqrtnum=Math.floor(Math.sqrt(num));
    var prime = num != 1;
    for(var i=2; i<sqrtnum+1; i++) { // sqrtnum+1
        if(num % i == 0) {
            prime = false;
            break;
        }
    }
    return prime;
}

现在的复杂度是O(sqrt(n))

更多信息请参见 为什么我们检查质数时只需要检查到其平方根？

希望对您有所帮助。

- Geeky

Answer 3

function isPrime(num) { // returns boolean
  if (num <= 1) return false; // negatives
  if (num % 2 == 0 && num > 2) return false; // even numbers
  const s = Math.sqrt(num); // store the square to loop faster
  for(let i = 3; i <= s; i += 2) { // start from 3, stop at the square, increment in twos
      if(num % i === 0) return false; // modulo shows a divisor was found
  }
  return true;
}
console.log(isPrime(121));

感谢 Zeph 纠正我的错误。

- Tomachi

---

请在您的代码中添加一些解释。这有助于人们理解算法，以便他们可以适应它，而不仅仅是复制您的代码。 - Mr. T

在数字9上失败了，因为sqrt(9) = 3，而你的循环没有被调用。 尝试使用 i <= s。 - ZephDavies

Answer 4

质数为形如6f ± 1，但不包括2和3，其中f是任意整数

 function isPrime(number)
 { 
   if (number <= 1)
   return false;

   // The check for the number 2 and 3
   if (number <= 3)
   return true;

   if (number%2 == 0 || number%3 == 0)
   return false;

   for (var i=5; i*i<=number; i=i+6)
   {
      if (number%i == 0 || number%(i+2) == 0)
      return false;
   }

   return true;
 }

算法的时间复杂度：O(根号n)

- H S W

Answer 5

酷炫版本：

const isPrime = n => ![...Array(n).keys()].slice(2).map(i => !(n%i)).includes(true) && ![0,1].includes(n)

- Sergio

---

&& ![0,1].includes(number)是用来做什么的？如果n等于1或0，没有这个检查也会得到相同的结果 - false。 - Jeremy Belolo

你能再详细说明一下吗？ - Vendetta

时间复杂度方面效率低下的解决方案。 - Ravi Chaudhary

Answer 6

function isPrimeNumber(n) {
  for (var i = 2; i < n; i++) { // i will always be less than the parameter so the condition below will never allow parameter to be divisible by itself ex. (7 % 7 = 0) which would return true
    if(n % i === 0) return false; // when parameter is divisible by i, it's not a prime number so return false
  }
  return n > 1; // otherwise it's a prime number so return true (it also must be greater than 1, reason for the n > 1 instead of true)
}

console.log(isPrimeNumber(1));  // returns false
console.log(isPrimeNumber(2));  // returns true
console.log(isPrimeNumber(9));  // returns false
console.log(isPrimeNumber(11)); // returns true

- Mary Pieroszkiewicz

---

如果您能够在翻译的内容中加入链接，那将非常好。 - Ezequiel De Simone

Answer 7

// A list prime numbers

function* Prime(number) { 
  const infinit = !number && number !== 0;
  const re = /^.?$|^(..+?)\1+$/;  
  let actual = 1;
 
  while (infinit || number-- ) {
      if(!re.test('1'.repeat(actual)) == true) yield actual;
      actual++
  };
};

let [...primers] = Prime(101); //Example
console.log(primers);

- arius

---

非常有趣的解决方案，但我完全不明白这里正在发生什么（使用正则表达式生成质数序列？）你能解释一下吗？ - HynekS

https://iluxonchik.github.io/regular-expression-check-if-number-is-prime/ - ulou

Answer 8

我会这样做：

const isPrime = (num) => num < 10 ? [2, 3, 5, 7].includes(num) : ![2, 3, 5, 7].some(i => !(num % i));

更新（感谢@lakscastro）：

export const isPrime = n => n <= 1 ? false : !Array.from(new Array(n), (el, i) => i + 1)
  .filter(x => x > 1 && x < n)
  .find(x => n % x === 0);

- Andrew Rusanov

---

你的答案不正确，这有太多误报的情况。我们在1000以内有168个质数，而你的函数却说我们有231个（从0到1000测试一下就会得到231个数字）。 - Alex Rintt

Answer 9

我认为这个问题需要一个递归解决方案：

// Preliminary screen to save our beloved CPUs from unneccessary labour

const isPrime = n => {
  if (n === 2 || n === 3) return true;
  if (n < 2 || n % 2 === 0) return false;

  return isPrimeRecursive(n);
}

// The recursive function itself, tail-call optimized.
// Iterate only over odd divisors (there's no point to iterate over even ones).
 
const isPrimeRecursive = (n, i = 3, limit = Math.floor(Math.sqrt(n))) => { 
  if (n % i === 0) return false;
  if (i >= limit) return true; // Heureka, we have a prime here!
  return isPrimeRecursive(n, i += 2, limit);
}

// Usage example

for (i = 0; i <= 50; i++) {
  console.log(`${i} is ${isPrime(i) ? `a` : `not a` } prime`);
}

这种方法存在缺点-由于浏览器引擎（截至2018年11月）仍然没有TC优化，如果按照数值顺序测试亿万级别或更高的素数，您可能会遇到文字堆栈溢出错误（可能因实际浏览器及可用内存而异）。

- HynekS

Answer 10

自 Node.js 16 版本开始，这是 内置 的：

import {checkPrimeSync as isPrime} from 'node:crypto';

console.log(isPrime(13));
//=> true

否则，@IhorSakaylyuk的答案可以进一步改进，通过跳过偶数：

function isPrime(number) {
    if((number % 2 === 0 && number !== 2) || number <= 1) {
        return false;
    }

    const limit = Math.floor(Math.sqrt(number));

    for(let index = 3; index <= limit; index += 2) {
        if (number % index === 0) {
            return false;
        }
    }

    return true;
}

我还创建了一个npm包，其中包含此函数。

- Richie Bendall