题解 | #判断质数#
判断质数
https://www.nowcoder.com/practice/b936f737e2b34b3199a7c875446edd06
1. 假如n是合数，必然存在非1的两个约数p1和p2，其中p1<=sqrt(n)，p2>=sqrt(n)。
2.质数还有一个特点，就是它总是等于 6x-1 或者 6x+1，其中 x 是大于等于1的自然数。
首先 6x 肯定不是质数，因为它能被 6 整除；其次 6x+2 肯定也不是质数，因为它还能被2整除；
依次类推，6x+3 肯定能被 3 整除；6x+4 肯定能被 2 整除。
那么，就只有 6x+1 和 6x+5 (即等同于6x-1) 可能是质数了。
所以循环的步长可以设为 6，然后每次只判断 6 两侧的数即可。
<body>
<script type="text/javascript">
// 补全代码
Number.prototype._isPrime = function(){
let num = +this;
// 小于或等于1非质数，2和3为质数
if (num <= 3) {
return num > 1;
}
// 优化：不在6的倍数两侧的一定不是质数
if (num % 6 != 1 && num % 6 != 5) {
return false;
}
//只需判断6的倍数两侧的数字是否为质数
let sqrt = Math.sqrt(num);
for (let i = 5; i <= sqrt; i += 6) {
if (num % i == 0 || num % (i + 2) == 0) {
return false;
}
}
return true;
}
</script>
</body>
腾讯一面1793人在聊