我正在尝试完成Codewars挑战，该挑战要求您检查一个数字是否为质数。无论出于何种原因，我的解决方案似乎不适用于奇素数的平方（例如9返回true而不是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));Ps 我包含了第二个 else/if 语句，因为我试图解决这个问题。
尽可能简单：
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))：
const isPrime = num => {
for(let i = 2, s = Math.sqrt(num); i <= s; i++)
if(num % i === 0) return false;
return num > 1;
}
这里有一个小建议，为什么要为整数 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))
希望能帮助到你
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 修正了我的错误。
酷版：
const isPrime = n => ![...Array(n).keys()].slice(2).map(i => !(n%i)).includes(true) && ![0,1].includes(n)
质数的形式为 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(sqrt(n))