JavaScript中的素数测试 [英] Number prime test in JavaScript

问题描述

我正在尝试完成 Codewars 挑战，要求您检查数字是否为质数.无论出于何种原因，我的解决方案似乎都不适用于奇质数的平方(例如，9返回true而不是false).

I'm trying to complete the Codewars challenge that asks you to check if a number is a prime number. For whatever reason, my solution doesn't seem to work for the square of odd prime numbers (e.g. 9 returns true instead of false).

function isPrime(num) {

  if (num === 2) {
    return true;
  } else if (num > 1) {
    for (var i = 2; i < num; i++) {

      if (num % i !== 0) {
        return true;
      } else if (num === i * i) {
        return false
      } else {
        return false;
      }
    }
  } else {
    return false;
  }

}

console.log(isPrime(121));

P.s.我加入了第二个else/if语句，因为我正试图解决问题.

P.s. I included that second else/if statement because I was trying to solve the problem.

推荐答案

尽可能简单:

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

使用ES6语法:

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

如果您运行循环直到数字的平方根，也可以将算法的复杂度从O(n)降低到O(sqrt(n)):

You can also decrease the complexity of the algorithm from O(n) to O(sqrt(n)) if you run the loop until square root of a number:

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

这篇关于JavaScript中的素数测试的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！