JavaScript判断数字是否为质数的方法汇总

前言

今天看到一个题目,让判断一个数字是否为质数.看上去好像不难.因此,我决定实现一下.

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循环来判断是否为质数

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整除的数字不计算

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判断数字是否为质数的方法汇总，希望对大家有所帮助.

赞 (0)

相关推荐

  • JavaScrpt判断一个数是否是质数的实例代码

    废话不多说了,直接给大家贴代码了 <script> //1.非正则实现 function isPrime(num) { // 不是数字或者数字小于2 if(typeof num !== "number" || !Number.isInteger(num)) { // Number.isInterget 判断是否为整数 return false } //2是质数 if(num == 2) { return true } else if(num % 2 == 0) { //排除

  • JavaScript实现找质数代码分享

    好吧,也没有背景说明,没有高深技能,纯粹无聊,想找出10000内的所有质数.那么就开始了: function zhishu(num) { if (num == 1) { return false; } if (num == 2) { return true; } for (var i = 2; i <= Math.sqrt(num); i++) { if (num % i == 0) { return false; } } return true; } 使用实例: var zhishuArray

  • JavaScript判断数字是否为质数的方法汇总

    JavaScript判断数字是否为质数的方法汇总

    前言 今天看到一个题目,让判断一个数字是否为质数.看上去好像不难.因此,我决定实现一下. DOM结构 <!DOCTYPE html> <html lang="en"> <head> <meta charset="UTF-8"> <title>计算500以内的质数并输出</title> <meta name="viewport" content="width=d

  • JavaScript判断是否为数组的各种方法汇总

    JavaScript判断是否为数组的各种方法汇总

    目录 前言 Array.isArray constructor instanceof isPrototypeOf Object.prototype.toString typeof 总结 前言 我们在日常开发中,常常有判断某值类型的需求,今天我们总结一下常见的几种用来判断是否为数组的 JavaScript 方法. Array.isArray Array.isArray() 是ES5新增的方法,用于确定传递的值是否是一个数组,如果是数组,则返回  true,否则返回 false. let arr =

  • python中判断数字是否为质数的实例讲解

    在计算机程序中,算法是灵魂,是程序的精髓所在.程序执行效率的高低直接取决于算法的优劣,所以计算机算法是计算机课程必修课.算法可以快速计算出我们所需要的结果,例如判断质数,这是很基础的内容,具体如何操作呢?下面小编向大家演示在python如何判断数字是否为质数. 质数:一个大于1的自然数,除了1和它本身外,不能被其他自然数(质数)整除(2, 3, 5, 7等),换句话说就是该数除了1和它本身以外不再有其他的因数. 判断代码: def isprime(a): if isinstance(a,int)

  • JavaScript判断变量是否为数组的方法(Array)

    今天小编给大家整理些关于javascript判断变量是否是数组(Array)的相关知识,主要通过以下四点给大家展开话题,具体内容如下所示: 1. typeof真的那么厉害吗?? //首先看代码 var ary = [1,23,4]; console.log(typeof ary); //输出结果是Object 上面的办法并不能实时的检测出是否是数组,只能判断其类型,所以说typeof判断基本类型数据还是挺好的,但是不能准确测试出是否是数组(typeof的具体用法以后提及,现在回归正题) 2.in

  • JavaScript判断文件上传类型的方法

    本文实例展示了JavaScript判断文件上传类型的方法,是一个非常常用的技巧.具体实现方法如下: 文件上传时用到一个功能,使用html元素的input标签实现: <input id="imageFile" name="imageFile1" accept="image/jpg,image/jpeg,image/png,image/bmp,image/gif" type="file" title="点击选择文件

  • javascript判断数组内是否重复的方法

    本文实例讲述了javascript判断数组内是否重复的方法.分享给大家供大家参考.具体如下: Array.prototype.del = function(){ var a = {}, c = [], l = this.length; for (var i = 0; i < l; i++) { var b = this[i]; var d = (typeof b) + b; if (a[d] === undefined) { c.push(b); a[d] = 1; } } return c;

  • javascript判断变量是否有值的方法

    本文实例讲述了javascript判断变量是否有值的方法.分享给大家供大家参考.具体分析如下: 例如: var a = null; var b = undefined; 以上这两种情况算作没有值 if(a !== null && a !== undefined) { // } // 为什么不能单用if(a !== null) { // } var a; a !== null; // true // 为什么不能单用if(a !== undefined) { // } var a = null

  • JavaScript判断按钮被点击的方法

    废话不多说了,直接给大家贴代码了. firfox版: <HTML> <meta http-equiv="Content-Type" content="text/html; charset=utf-8" /> <HEAD> <TITLE></TITLE> <script> document.onclick=function(e){ var evt=e||window.event; var tar=

  • javascript将数字转换整数金额大写的方法

    本文实例讲述了javascript将数字转换整数金额大写的方法.分享给大家供大家参考.具体实现方法如下: 复制代码 代码如下: function digit_uppercase(n) { var digit = [ '零', '壹', '贰', '叁', '肆', '伍', '陆', '柒', '捌', '玖' ]; var unit = [ ['元', '万', '亿'], ['', '拾', '佰', '仟'] ]; var s = ''; for (var i = 0; i < unit[

  • 对python 判断数字是否小于0的方法详解

    为了精度更准确 可以使用数字的绝对值 < 1.0e-16  或者 < 1.0e-8来对比 abs(Num) <  1.0e-16 以上这篇对python 判断数字是否小于0的方法详解就是小编分享给大家的全部内容了,希望能给大家一个参考,也希望大家多多支持我们.

随机推荐