本文汇总了JavaScript中判断质数的多种实现方式，从基础的FOR循环到基于正则表达式的技巧。通过多次实测对比，分析了不同优化策略（如限制循环范围、排除特定尾数、利用平方根等）对执行效率的影响，并指出部分看似优化的逻辑反而导致负优化。
前言与DOM结构
前言
近期遇到一个编程题目，要求判断给定数字是否为质数。看似简单，于是决定动手实现并探讨不同方案。
DOM结构
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<title>计算500以内的质数并输出</title>
<meta name="viewport" content="width=device-width, initial-scale=1.0, maximum-scale=1.0, user-scalable=0">
<script src="http://apps.bdimg.com/libs/jquery/2.1.4/jquery.min.js"></script>
</head>
<body>
<div class="echo">
<input type="text" id="num" value="">
<input type="button" id="submit" value="提交">
</div>
</body>
</html>
<script>
$(function(){
$("#submit").on('click',function(){
var num = $("#num").val();
if (isPrimeNum(num)) {
alert(num+"是质数");
}else{
alert(num+"是合数");
}
});
});
</script>如前文所示，核心逻辑封装在 isPrimeNum(num) 函数中。接下来将逐步实现该函数。
基础FOR循环实现
通过FOR循环来判断是否为质数
function isPrimeNum(num){
for (var i = 2; i < num; i++) {
if (num%i==0){
return false;
}
};
return true;
}原理比较简单,通过2以上的数字不断和目标数字求余数,如果能得到0,就表示这是一个合数而不是质数.
不过，这种全量遍历的运算量似乎有些大。
循环范围优化
优化一下第一个方法
实现起来并不复杂，但显然还有优化空间。既然只需判断是否有因子，循环至目标数的一半即可确定结果。
function isPrimeNum(num){
for (var i = 2; i < num/2+1; i++) {
if (num%i==0){
return false;
}
};
return true;
}尾数过滤与类型校验
实测发现速度确实有显著提升。但进一步思考，若数字尾数为偶数或5，则必然不是质数，无需继续计算。因此再次优化。
不计算数字尾数为双数或者5的数字
function isPrimeNum(num){
if (!isDual(num)){
return false;
}
for (var i = 2; i < num/2+1; i++) {
if (num%i==0){
return false;
}
};
return true;
}
function isDual(num){
var num = num.toString();
var lastNum = num.substring(num.length-1,num.length);
return lastNum%2 == 0 || lastNum%5 == 0 ? false : true;
}通过此类优化，理论上可大幅减少计算量（至少减半）。但实测性能提升并不明显，因为这类数字本就能快速被判定为非质数。
此处发现 substring() 函数仅适用于字符串，故先将数字转换为字符串处理。
如果不是数字或者整数的处理
若用户输入非数字或小数，如何处理？为此编写了两个辅助方法进行校验。
function isPrimeNum(num){
if (!isNum(num)){
return false;
}
if (!isInteger(num)){
return false;
}
if (!isDual(num)){
return false;
}
for (var i = 2; i < num/2+1; i++) {
if (num%i==0){
return false;
}
};
return true;
}
function isInteger(num){
return num == ~~num ? true : false;
}
function isNum(num){
return num == +num ? true : false;
}
function isDual(num){
var num = num.toString();
var lastNum = num.substring(num.length-1,num.length);
return lastNum%2 == 0 || lastNum%5 == 0 ? false : true;
}这里运用了两个技巧：一是使用 ~~num 对小数取整，二是利用 +num 将字符串转为数字。
了解更多请阅读我之前的博文《javascript 学习小结 JS装逼技巧(一) by FungLeo》
这并未显著提升效能，主要作用是过滤错误输入。再思考是否有更快速的非质数判定方法？
被3整除判定与循环上限调整
去除能被3整除的数字不计算
function isPrimeNum(num){
if (!isNum(num)){
return false;
}
if (!isInteger(num)){
return false;
}
if (num==2||num==3||num==5) {
return true;
}
if (!isDual(num)){
return false;
}
if (!isThree(num)){
return false;
}
for (var i = 2; i < num/5+1; i++) {
if (num%i==0){
return false;
}
};
return true;
}
function isInteger(num){
return num == ~~num ? true : false;
}
function isNum(num){
return num == +num ? true : false;
}
function isDual(num){
var num = num.toString();
var lastNum = num.substring(num.length-1,num.length);
return lastNum%2 == 0 || lastNum%5 == 0 ? false : true;
}
function isThree(num){
var str = num.toString();
var sum = 0;
for (var i = 0; i < str.length; i++) {
sum += +str.substring(i,i+1);
};
return sum%3 == 0 ? false : true;
}将数字转为字符串，拆分各位数字并求和，再对3取余，即可判断原数是否能被3整除。
自认为聪明……实测性能提升有限，虽有一定改善，但效果不如预期。
既然排除了3的倍数，循环上限无需至一半，只需至三分之一即可。同理，排除5后，循环至五分之一即可。
迅速调整后，效率确实大幅提升！效果显著。
但需注意，对于 2、3、5 这三个质数，上述逻辑可能误判为合数，因此需补充特殊处理。
if (num==2||num==3||num==5) {return true;}正则表达式方案与性能对比
别人的方法
想不到更优解，于是搜索其他方案，结果令人惊讶。
function isPrimeNum2(num){
return !/^.?$|^(..+?)\1+$/.test(Array(num + 1).join('1'))
}该方法使用正则表达式，代码极其简短，但原理晦涩难懂。
实在不解其原理，于是实测对比，发现我的代码效率远高于此正则方案。可见我的方法仍具优势。
实测打印100000以内所有质数，我的代码耗时1600ms，而正则代码需160000ms，即我的代码耗时仅为百分之一。
不过，谁能看懂这段代码请帮我解释一下…。
平方根优化与最终结论
补充
查阅相关资料，发现此前使用 num/5 的方式虽结果正确但非最优。更科学的方式是使用 Math.sqrt(num) 求平方根作为循环上限。
我的代码的测试结果如下
如上图所示，我的代码计算结果完全正确，但耗时1638毫秒。多次测试结果一致。
求平方根方式测试结果如下
如上图所示，采用平方根方式更为科学且速度更快。多次测试耗时在1150毫秒到1250毫秒之间，相比原代码性能提升约25%。
此前既判断尾数是否为双数或5，又判断各位和能否被3整除，旨在减少运算量。但这些额外判断本身也消耗计算资源。去除这些冗余代码后重新评估。
性能再次提升，看来之前的那些复杂计算实为负优化。
最终,代码如下:
function isPrimeNum(num){
if (!isNum(num)){
return false;
}
if (!isInteger(num)){
return false;
}
for (var i = 2; i <= Math.sqrt(num); i++) {
if (num%i==0){
return false;
}
};
return true;
}
function isInteger(num){
return num == ~~num ? true : false;
}
function isNum(num){
return num == +num ? true : false;
}小结:完全是我算术不好导致我在前面各种自作聪明.不过,练练小技巧也是好的-_-|||
最后看下计算100万以内的所有质数需要多长时间
以上所述是小编给大家介绍的JavaScript判断数字是否为质数的方法汇总，希望对大家有所帮助。