质数判定的几种方法及性能优化

[广告:最高 ¥2000 红包]阿里云服务器、主机等产品通用,可叠加官网常规优惠使用 | 限时领取

文章内容

  • 素性测试 (Primality test)
  • 什么是质数?
  • 遍历取模
  • 遍历取模函数式版本
  • 正则表达式法
  • 开方优化
  • 埃拉托斯特尼筛法:用质数找出质数
  • 性能比较

最近在刷笔试题,有几个关于质数的题目,总结一下判断是否为质数的几个方法。

素性测试 (Primality test)

素性测试或素数判定,是检验一个给定的整数是否为素数的测试。 维基百科

什么是质数?

质数(Prime number,又称素数),指在大于1的自然数中,除了1和该数自身外,无法被其他自然数整除的数(也可定义为只有1与该数本身两个正因数的数)。

大于1的自然数若不是素数,则称之为合数(也称为合成数)。

遍历取模

判断当前整数是否为质数最常规的方法,就是让它与所有小于它的数(且大于1)取模。

取模运算是求两个数相除的余数。余数为0,说明能被整除。

只要能被其中一个数整除即为合数,不能被所有整除即为质数。

以上代码时间复杂度为:O(n),被检测的数越大,在经历的循环次数越多,耗时越大。

...
...
9: 0.030ms
10 false
10: 0.025ms
11 true
11: 0.025ms
197 true
197: 0.034ms
977 true
977: 0.063ms
7919 true
7919: 0.362ms
51977 true
51977: 2.624ms
99991 true
99991: 1.359ms
999983 true
999983: 5.989ms
999987 false
999987: 0.024ms
1000000007 true
1000000007: 6007.705ms
12345678911 false
12345678911: 0.046ms

如上,需要6秒钟才能判断1000000007是个质数。

遍历取模函数式版本

可以用数组方法替代for循环。

坏处就是需要生成一个1至n的数组,增加了空间复杂度。n越大,数组越大。

虽然JavaScript中数组长度的最大值为 2**32-1,但实际上肯定到不到2**32-1,如10000000000就不行了。可能跟电脑的配置有关。

因无法生成1000000007长度的数组,以上代码无法检测出1000000007等一系列大的质数。

正则表达式法

这个方法很酷,详细的解释,请戳:A wild way to check if a number is prime using a regular expression | by Mark Sauer-Utley | ITNEXT

https://itnext.io/a-wild-way-to-check-if-a-number-is-prime-using-a-regular-expression-4edfb725f895

简单解释:

^1?$|^(11+?)\1+$

这个正则表达式可以匹配所有不是质数的数(合数,以及0,1),模式如下图所示:

这个正则表达式主要是通过将数值转化为字符1的个数来实现监测质数的功能的。此正则表达式分成 由”|”分割两部分: /^1?$//^(11+?)\1+$/

前一部分匹配0或1,这两个数不是质数。

后一部分(11+?)表示至少有两个1,(11+?)\1中的\1表示对前面的匹配的引用。\1+表示前面的(11+?)出现至少一次,相当于(11+?){2,}。整个式子的含义为至少出现两次(11+?)。也就是说,所匹配的数可以写成两个大于2的整数的乘积。而?通过backtrace穷举所有的可能行,从而完成匹配所有的合数。

因此,两部分使用|连接,不匹配的就只能是质数了。

存在问题:

需要生成  “1”.repeat(n)  的字符串,n越大,字符串越大,空间复杂度越大。

同样,理论上js字符串的长度为2**53-1,实际上1000000000就不行了。

100000000可以,但其内存占用100mb以上。

所以正则表达式方法也检测不了大的质数。

开方优化

以上方案中,遍历取模是适用而比较广的,它能检测到质数相对较大。

只要想办法减少遍历次数,即可提升性能。

因为一个数的最小质因数一定会小于或等于这个数的开方(平方根)。

质因数素因数质因子)在数论里是指能整除给定正整数质数。除了1以外,两个没有其他共同质因子的正整数称为互质

  • 1没有质因子。
  • 5只有1个质因子,5本身。(5是质数)
  • 6的质因子是2和3。(6 = 2 × 3)
  • 2、4、8、16等只有1个质因子:2。(2是质数,4 =2²,8 = 2³,如此类推)
  • 10有2个质因子:2和5。(10 = 2 × 5)

如100的开方是10,其质因数 2和5都小于10。121的质因数11,等于其开方11。

因为一个数的最小质因数小于或等于其开方,所以只需要遍历到其开方数就可以了。

其性能大大提升。

筛法:用质数查找质数

开方优化方法将循环次数从n减少到Math.sqrt(n),性能大幅度提升。

那么能否进一步减少循环次数?答案是肯定的。

遍历取模是对质数才有效,在有限的整数序列中,质数远少于合数。如果只对质数集合遍历,将大大循环次数。

所以,关键在于找出小于Math.sqrt(n)的质数集合。

此时需用筛法:筛法(挨拉托色尼筛法)是一种用来求所有小于N的素数的方法。把从2(素数是指大于1的自然数)开始的某一范围内的正整数从小到大按顺序排列,逐步筛掉非素数留下素数。

筛法求素数的基本思想是:把从2到N的一组正整数从小到大按顺序排列。从中依次删除2的倍数、3的倍数、5的倍数,直到根号N的倍数为止,剩余的即为2~N之间的所有素数。

所以,100以内的素数都可以通过2,3,5,7筛选出来:

代码实现即为:

我们需要一个[2,3,5,7… Math.sqrt(n)]集合,可以通过生成器实现:

genPrimes将生成一个质数有序集合,判定质数只需对该集合遍历取模就行。

性能比较

筛法  ≈>  开方优化

筛法法因维护ALL_PRIMES集合,必然增加算法空间复杂度。所以在数值较小时,筛法与简单开方优化差不多。

但数值越大,筛法时间效率越高。

开方优化>>遍历取模>函数式遍历取模>正则表达式。

你还知道哪些质数判定的方法,请留言告诉我!

参考资料

码中人 微信公众号

1 thought on “质数判定的几种方法及性能优化

Comments are closed.