这篇文章主要介绍了 JavaScript 判断数字是否为质数的方法汇总的相关资料, 非常不错具有参考借鉴价值,需要的朋友可以参考下
Javascript 是一种由 Netscape 的 LiveScript 发展而来的原型化继承的基于对象的动态类型的区分大小写的客户端脚本语言,主要目的是为了解决服务器端语言,比如 Perl,遗留的速度问题,为客户提供更流畅的浏览效果。
前言
今天看到一个题目, 让判断一个数字是否为质数. 看上去好像不难. 因此, 我决定实现一下.
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 万以内的所有质数需要多长时间
来源: http://www.phperz.com/article/17/0402/265218.html