查找质数公式(快速计算质数)
先列举一个口算方法:假设计算120以内的质数可以把2、3、5、7先列出来,然后从6开始往后,每次加6得一偶数(12、18、24…),然后计算该偶数的相邻奇数是否是质数,计算方法是,首先将个位为5(比如25)的奇数直接pass,在49之前只需计算能否被3整除,即11、13(12的相邻奇数)、17、19(18的相邻奇数)、23(24的相邻奇数,pass掉25)、29、31(30的相邻奇数)、37(36的相邻奇数pass掉35)、41、43(42的相邻奇数)、47(48的相邻奇数)只需计算能否被3整除;在48之后121之前的6的倍数的相邻奇数只需计算能否被3、7整除(比如113=114-1只需计算能否被3、7整除),3、7都不能整除就是质数(延伸:121=11*11至168=13*13-1则只需要计算3、7、11……),今天小编就来聊一聊关于查找质数公式?接下来我们就一起去研究一下吧!
查找质数公式
先列举一个口算方法:假设计算120以内的质数。可以把2、3、5、7先列出来,然后从6开始往后,每次加6得一偶数(12、18、24…),然后计算该偶数的相邻奇数是否是质数,计算方法是,首先将个位为5(比如25)的奇数直接pass,在49之前只需计算能否被3整除,即11、13(12的相邻奇数)、17、19(18的相邻奇数)、23(24的相邻奇数,pass掉25)、29、31(30的相邻奇数)、37(36的相邻奇数pass掉35)、41、43(42的相邻奇数)、47(48的相邻奇数)只需计算能否被3整除;在48之后121之前的6的倍数的相邻奇数只需计算能否被3、7整除(比如113=114-1只需计算能否被3、7整除),3、7都不能整除就是质数。(延伸:121=11*11至168=13*13-1则只需要计算3、7、11……)。
质数的定义:大于1且只能被1和自身整除的自然数(如:2、3、5、7、11等)。
合数的定义:大于1且不是质数的自然数(如:4,6,8,9,10等)。
简单地根据质数的定义,要判断一个数N是否是质数,需要证明2至N-1的自然数都不能整除N,然而事实上很多自然数是可以直接排除质数之外的,比如一个偶数,很明显能被2整除,又比如位数为5的奇数,很明显能被5整除,也无需计算。
本文将介绍质数的快速计算方法。比如,如何快速计算出自然数M(M可以足够大)以内的质数;又比如,在大质数的计算中(通常是用计算机编程计算),如何快速计算一个大数是否是质数。
一、减少需要计算的数
由于除2以外的所有偶数均可以排除,也就是说,除2之外的所有偶数都是合数,无需计算;需要计算的奇数可以定义为:2n 1(或2n-1),n为自然数;或4n 1及4n 3(可以用4n-1代替);或6n 1,6n 3,6n 5(可以用6n-1替代);或8n 1,8n 3,8n 5(8n-3),8n 7(8n-1)……
2n 1方式需要对所有奇数进行计算,未达到减少计算数的目的。
4n 1及4n-1方式也不能减少计算数,因为4*2 1及4*4-1都是合数,而4*2-1和4*4 1都是质数,无法直接减少计算数,也未达到减少计算数的目的。
8n方式可以用8n1及8n3也无法减少计算数(8*1 1,8*2-1,8*33都是合数,所以必须全部运算),也未达到减少计算数的目的。
对于6n1及6n 3方式而言,由于6n 3能被3整除,是无需计算就能排除是质数的,所以用6n1及6n 3方式计算只需要计算6n1,减少了6n 3的判断。比如说:计算100以内的质数,2、3以上可以只计算6*1-1(5)、6*1 1(7),6*2-1(11)、6*2 1(13),6*3-1(17)、6*3 1(19)……,而9(6*1 3)、15(6*2 3)、21……等奇数是无需计算的,这样就减少了需要计算的数了(准确地说,每3个奇数可以减少1个计算数)。
如果感兴趣,可以从8往后再看看,10n…方式每5个奇数可以减少1个计算数;12n方式每6个奇数可以减少2个计算数,但表达式较6n方式麻烦,且实质上参与运算的数是一样的;14n方式每7个奇数可以减少1个计算数……。
二、减少计算量
如上节述,2、3以外,可以用计算6n1是否是质数(口算就是从6开始,计算6的倍数的两个相邻数(6计算5、7,12计算11、13;18计算17、19,24计算23、25……)是否为质数。
对于每一个需要计算的数,可以用以下方法减少计算量:
对于一个数N(N可以任意大),N的算术平方根的整数部分为x,如果N不能被小于或等于x的任意质数整除,则N为质数(换言之:计算N是否为质数可以只计算小于或等于x的质数能否整除N)。
能用该算法减少计算量的原因:如果N为合数,则N一定能分解成2个以上的质因数,其中最小的一个质因数一定不会大于x。
三、综合
计算一个自然数M(M可以足够大)以内的质数,可以2、3、5、7先列出来,然后从6开始,每次加6得一偶数,计算该偶数的相邻奇数是否是质数,口算方法是,首先将个位为5(比如25)的直接pass,在49之前只需计算能否被3整除(5已经一眼排除),在48之后的6的倍数的相邻奇数只需计算能否被3、7整除(3、7都不能整除就是质数)。(121-168则只需要计算3、7、11;169至288=17*17-1只需计算3、7、11、13……)。在计算大奇数是否为质数时,由于不是口算而是用计算机编程计算,就要把5纳入运算,可以建一队列从小到大依次将计算出的质数保存在队列中,然后对N=6n1的每一个奇数计算,依次计算3、5、7……、x(x为N的算术平方根的整数部分)是否能整除N即可。
免责声明:本文仅代表文章作者的个人观点,与本站无关。其原创性、真实性以及文中陈述文字和内容未经本站证实,对本文以及其中全部或者部分内容文字的真实性、完整性和原创性本站不作任何保证或承诺,请读者仅作参考,并自行核实相关内容。文章投诉邮箱:anhduc.ph@yahoo.com