判断一个数是否是质数
程序员文章站
2024-03-15 13:10:59
...
效率地判断一个数是否是质数
题:写一个isPrime()函数,当其为质数时返回true,否则返回false。
思路简述:
1、首先, 因为JavaScript不同于C或者Java,因此你不能信任传递来的数据类型。如果没有明确地告诉你,你应该询问他是否需要做输入检查,还是不进行检查直接写函数。严格上说,应该对函数的输入进行检查。
2、要记住:负数不是质数。同样的,1和0也不是,因此,首先测试这些数字。此外,2是质数中唯一的偶数。没有必要用一个循环来验证4,6,8。再则,如果一个数字不能被2整除,那么它不能被4,6,8等整除。因此,你的循环必须跳过这些数字。如果你测试输入偶数,你的算法将慢2倍(你测试双倍数字)。可以采取其他一些更明智的优化手段,我这里采用的是适用于大多数情况的。例如,如果一个数字不能被5整除,它也不会被5的倍数整除。所以,没有必要检测10,15,20等等。如果你深入了解这个问题的解决方案,我建议你去看相关的Wikipedia介绍。
3、最后一点,你不需要检查比输入数字的开方还要大的数字。我感觉人们会遗漏掉这一点,并且也不会因为此而获得消极的反馈。但是,展示出这一方面的知识会给你额外加分。
//最后贴上代码
function isPrime(number) {
// If your browser doesn't support the method Number.isInteger of ECMAScript 6,
// you can implement your own pretty easily
if (typeof number !== 'number' || !Number.isInteger(number)) {
// Alternatively you can throw an error.
return false;
}
if (number < 2) {
return false;
}
if (number === 2) {
return true;
} else if (number % 2 === 0) {
return false;
}
var squareRoot = Math.sqrt(number);
for(var i = 3; i <= squareRoot; i += 2) {
if (number % i === 0) {
return false;
}
}
return true;
}
下一篇: 判断一个数是否是素/质数