您现在的位置: 首页 > 网站导航收录 > 百科知识百科知识

质数是什么(快速计算质数)

质数,奇数,自然数质数是什么(快速计算质数)

发布时间：2019-02-08加入收藏来源：互联网点击：

先列举一个口算方法：假设计算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即可。

本文到此结束，希望对大家有所帮助呢。