你的位置:主页 > 赛场实况 >

判断一个数是否为质数/素数——从普通判断算

2020-07-17 | 人围观

  最直观的方法,根据定义,因为质数除了1和本身之外没有其他约数,所以判断n是否为质数,根据定义直接判断从2到n-1是否存在n的约数即可。C++代码如下:

  上述判断方法,明显存在效率极低的问题。对于每个数n,其实并不需要从2判断到n-1,我们知道,一个数若可以进行因数分解,那么分解时得到的两个数一定是一个小于等于sqrt(n),一个大于等于sqrt(n),据此,上述代码中并不需要遍历到n-1,遍历到sqrt(n)即可,因为若sqrt(n)左侧找不到约数,那么右侧也一定找不到约数。C++代码如下:

  方法(2)应该是最常见的判断算法了,时间复杂度O(sqrt(n)),速度上比方法(1)的O(n)快得多。最近在网上偶然看到另一种更高效的方法,暂且称为方法(3)吧,由于找不到原始的出处,这里就不贴出链接了,如果有原创者看到,烦请联系我,必定补上版权引用。下面讲一下这种更快速的判断方法;

  首先看一个关于质数分布的规律:大于等于5的质数一定和6的倍数相邻。例如5和7,11和13,17和19等等;

  证明:令x≥1,将大于等于5的自然数表示如下:······ 6x-1,6x,6x+1,6x+2,6x+3,6x+4,6x+5,6(x+1),6(x+1)+1 ······可以看到,不在6的倍数两侧,即6x两侧的数为6x+2,6x+3,6x+4,由于2(3x+1),3(2x+1),2(3x+2),所以它们一定不是素数,再除去6x本身,显然,素数要出现只可能出现在6x的相邻两侧。这里有个题外话,关于孪生素数,有兴趣的道友可以再另行了解一下,由于与我们主题无关,暂且跳过。这里要注意的一点是,在6的倍数相邻两侧并不是一定就是质数。此时判断质数可以6个为单元快进,即将方法(2)循环中i++步长加大为6,加快判断速度,原因是,假如要判定的数为n,则n必定是6x-1或6x+1的形式,对于循环中6i-1,6i,6i+1,6i+2,6i+3,6i+4,其中如果n能被6i,6i+2,6i+4整除,则n至少得是一个偶数,但是6x-1或6x+1的形式明显是一个奇数,故不成立;另外,如果n能被6i+3整除,则n至少能被3整除,但是6x能被3整除,故6x-1或6x+1(即n)不可能被3整除,故不成立。综上,循环中只需要考虑6i-1和6i+1的情况,即循环的步长可以定为6,每次判断循环变量k和k+2的情况即可,理论上讲整体速度应该会是方法(2)的3倍。代码如下:

  算法性能测试:编写测试代码,使用较多数据测试比较几种方法的判断效率,数据量40w,代码如下:

  运行结果如下;

  

  可以看出,判断到40w,效率上方法(1)明显要差得多,方法(2)和方法(3)在这种测试数量下时间相差2倍多

标签:
Top