js判断一个数是否是素数/质数

js判断一个数是否是素数/质数

月光魔力鸭

2018-10-22 17:02 阅读 591 喜欢 1 js判断素数

我们经常会有判断一个数值是素数的需求,那么我们如何来实现呢?

首先,我们来看下关于“素数”的定义,在抛开程序范畴的情况下,如何定义一个数值是素数?

质数(prime number)又称素数,有无限个。 质数定义为在大于1的自然数中,除了1和它本身以外不再有其他因数。

关于素数的个数是无限的,可以通过反证法来证明,如下:

质数的个数是无穷的。欧几里得的《几何原本》中有一个经典的证明。它使用了证明常用的方法:反证法。具体证明如下:假设质数只有有限的n个,从小到大依次排列为p1,p2,……,pn,设N=p1×p2×……×pn,那么,  是素数或者不是素数。
如果  为素数,则  要大于p1,p2,……,pn,所以它不在那些假设的素数集合中。
1、如果 为合数,因为任何一个合数都可以分解为几个素数的积;而N和N+1的最大公约数是1,所以不可能被p1,p2,……,pn整除,所以该合数分解得到的素因数肯定不在假设的素数集合中。因此无论该数是素数还是合数,都意味着在假设的有限个素数之外还存在着其他素数。所以原先的假设不成立。也就是说,素数有无穷多个。
2、其他数学家给出了一些不同的证明。欧拉利用黎曼函数证明了全部素数的倒数之和是发散的,恩斯特·库默的证明更为简洁,哈里·弗斯滕伯格则用拓扑学加以证明。

当我们了解了一个素数的定义后,我们就可以通过程序来计算或判断是否是素数。

实现1

我们可以通过轮询来判断该数值是否可以被其他数值进行整除,那么实现如下:

function isPrime(n){
  //1.首先明白,n是大于1的自然数;2.如果n为2,那么n为素数。
  if(n === 2 ){return true;}
  for(let i=2;i<n;i++){
    if(n % i === 0){
      return false;
    }
  }
  return true;
}

如上所示,我们根据这个函数进行一个测试,获得第N个素数,看下会使用多久的时间计算出来。

//获得第几个素数
function getPrime(n){
  var arr = [];
  var start = 2;
  while(arr.length < n){
    if(isPrime(start)){
      arr.push(start);
    }
    start ++ ;
  }
  return arr[arr.length -1];
}

当我们数量达到50000的时候,会发现时间明显的非常长了,大约耗费了70s时间,很明显还会有优化的空间。

实现2

我们继续了解素数的定义,会发现所有的偶数都不会是素数,素数只能是奇数。而且,我们的循环也可以抛开偶数进行循环,那么次数又会减少不少,如下:

function isPrime(n){
  if(n === 2){
    return true;
  }else if(n % 2 === 0 ){
    return false;
  }
  var r = Math.sqrt(n);
  for(let i=3;i<=r;i+=2){
    if(n % i === 0){
      return false;
    }
  }
  return true;
}

当我们使用以上实现来获得的时候,会发现,消耗时间减少数倍,当然,结果肯定是相同的。

之后测试到百万级别的时候发现已经消耗时间较长了,达到8s,当然,仍然比第一个方法更少的消耗时间,当到千万级别的时候,就开始明显的提升了。

转载请注明出处: https://chrunlee.cn/article/js-is-prime.html


如果对你有用的话,请赏给作者一个馒头吧 ...或帮点下页面底部的广告,感谢!!

赞赏支持
提交评论
评论信息(请文明评论)
暂无评论,快来快来写想法...
推荐
在页面中不同的frame之间进行相互调用的话,我们可以通过frame获取对应的window然后进行调用,但是如果是浏览器不同的tab之间呢?
做作业的时候,需要在手机上预览下,但是发现如果想在移动端上展示A4样子的作业还是挺麻烦的,最后还是准备通过图片来展示,然后移动端缩放呗。。
需求如下:有一张大图,需要显示大图中的一小部分,目前能知道的时候小图的宽高和坐标,同时大图有一个旋转角度可以知道,目标就是把小图正确的显示出来。
在web开发过程中,现在JSON 已经到了俯拾皆是的地步了,操作JSON对于JS来说非常简单,那么我们对于JSON的转化是如何应对的呢?
对于web开发过程中的JS对象 Array ,我们真的充分使用了么?是不是理解了Array的全部?能够在合适的地点调用合适的函数,使用合适的属性?
在开发过程中多个页面使用的一个小工具类,简单完善了下,还算不错,给各位提供下小思路。
最大公因数,也称最大公约数、最大公因子,指两个或多个整数共有约数中最大的一个。a,b的最大公约数记为(a,b),同样的,a,b,c的最大公约数记为(a,b,c),多个整数的最大公约数也有同样的记号。求最大公约数有多种方法,常见的有质因数分解法、短除法、辗转相除法、更相减损法。与最大公约数相对应的概念是最小公倍数,a,b的最小公倍数记为[a,b]。
this 是 JavaScript 的一大难点,多年经验的前端程序员都可能对这方面模糊。this 在大量的函数、类库中都有使用,理清显式绑定和隐式绑定有助于理解或书写这类函数。