素数极限问题探讨

付媛媛　钱俊彤　钱冠州　马铭里

【摘要】随着自然数的不断增大，素数的个数也在不断增多，而素数的不断增加导致因数数目的不断扩大，这是否意味着自然数、因数增加到一定程度后所有的自然数都能够被1和自身以外的因数分解而没有新的素数了呢？借助计算机对自然数中所蕴涵的素数进行计算、统计分析，其规律显示素数个数将随着自然数的增大而增加下去，素数是没有尾的.此次借助计算机算出的最大一个素数是2099999999.

【关键词】素数；自然数；因数

素数即只能被1和它自身整除的自然数.随着自然数的不断增大，素数的个数也在不断增多，就意味着因数的不断增加.自然数的不断增大和因数的增多就意味着素数的个数就可能要减少，那么当自然数大到某个数后，是否就没有素数了，就是说素数是否有尾呢？借助计算机对素数个数进行计算、统计、分析，显示出二者的变化关系趋势.

1.素数的算法

算法1：根据素数的定义，判定某个自然数n是否为素数，只需用2到n-1去除n，如果都除不尽则n是素数，否则只要其中有一个数能整除则n不是素数.这种根据定义计算素数需要执行n-2次除法，计算量大，当分析计算较大自然数的素数时耗时长.

优化算法2：很显然，当因数大于自然数n的一半，即n/2时，只剩1个因数n可以整除n，故在判定自然数n是否为素数只需计算2～n/2范围内有无因数即可，计算工作量较算法1减少一半.

优化算法3：若n能分解成因数i×j（i，j是大于2，小于n的整数），则i、j取值范围为：大于等于2而小于等于n/2，因数i、j所组成的数列中按大小顺序排列二者具有关系i×j=n，如图1所示.数列的中心位置为n，故从2计算到n是否有因数存在即可判断出n是否为素数，而从n到n/2实际上是重复计算.这种算法较算法2计算量减少n/2，当n较大，例如为1亿时，计算量仅为算法2的1/5000，计算量大幅减少.

优化算法4：在计算机编程计算时可进一步优化计算工作量.首先，自然数n的末位数为偶数或5时则该数可以被2或5整除，故该自然数一定不是素数.在编程时可以只对末位数为除5以外的奇数进行素数判断，进一步减少需要进行素数判断的自然数.其次，在算法3中因数i取值范围2～n，末位数为偶数或5的因数进行i×j=n的运算结果必然是末位数为偶数或5的自然数n，故对于需要进行判断的末位数为除5以外的奇数自然数n而言末位数为偶数或5的因数i一定不是自然数n的因数.在自然数n与因数i的整除运算判断素数是因数i的实际运算范围可以确定为3～n中末位数为除5以外的奇数，这样可以进一步减少计算机运算工作量.

通过上述分析对比可见经过3步优化后计算量大幅度减少，且当计算的自然数n越大时，其算法的优越性更加明显.例如在计算出1亿～2亿之间的自然数n的所有素数时，算法1的整除运算量为1016次，而算法4的整除运算量为1.6×1011次，提高效率6.2×104倍.

2.计算结果分析

由于个人PC机性能及时间因素限制，只分析计算到自然数21亿以内的素数.经过约半年时间运算得到的21亿以内最大的素数是2099999999，并对21亿以内的素数数量变化趋势进行分析.

首先，看一下自然数1亿到21亿之间素数数量变化规律.图2显示了自然数每增加1亿，这一亿自然数之间对应的素数个数.显然素数个数随着自然数的增加、因数相应增加，素数在每一亿自然数区间内个数减少，即自然数每增加1亿，在这新增加的1亿自然数中所包含的素数个数是在递减的（图2），因此有了文章一开始的疑问：随着自然数增大素数个数会减少，是否在自然数大于某个数后，素数个数增加值为零呢？也就是说素数似乎应该有个尾？

其次，再来看一下随着自然数的增加对应的素数总数增量关系.在图2的线性坐标系中显示的素数个数在每一亿自然数区间非线性减少，具有渐近X轴趋势，似乎是一种无限接近而又不能到达X轴，因此在双对数坐标系中查看二者关系有什么变化趋势.图3显示了素数总数-自然数在双对数坐标系中非线性变化关系：自然数每增加一个数量级（10倍），小于这个自然数的所有素数总个数也增加若干倍，但素数增加倍数小于10（表1），且二者呈非线性关系增加（图3），由于二者关系曲线在Y=X曲线下方，显然素数增加的速度小于自然数，而且曲线呈下凸特征，没有渐近水平趋势，即素数总个数没有趋于某一上限趋势，也就是说素数总数将会随着自然数增加而无限增加下去.表1中自然数按10倍比例关系继续增加下去可以构成一组比例为10的等比正项级数数列.随着自然数的10倍关系增加素数总个数呈大于6倍的比例关系增加，而且随着自然数的增加，素数增加的倍数也在增大，且有渐近10的趋势（表1），当然其增加的比例关系上限不可能超过自然数增加的倍数10，即图3中素数曲线有接近Y=X曲线趋势但不会超越.

差值素数倍数大10倍而增加的倍数素数总数随自然数扩最大素数值素数总个数最大自然数

3.结论

通过上述分析可知，由自然数和素数的总个数可组成自然数、素数两个数列，即表1中的自然数、素数个数项所组成的数列，自然数数列以10倍的关系无限增加下去，相应的素数总个数所组成的数列呈大于6倍的关系相应的增加下去，根据达朗贝尔正项级数比值审敛判别法可知：由自然数、素数的个数所构成的2个正项级数都是发散的.故素数将随着自然数的增加而不断的增多，即素数没有尽头.

此次利用计算机算出的约1亿个素数中最大一个素数是2099999999.

【参考文献】

[ 1 ]魏贵民.高等数学[M].北京：地质出版社，1999.

[ 2 ]王云葵，马武瑜.关于判别素数的充要条件[J].延安大学学报.2001，20（1），18-20.

[ 3 ]崔彩霞.素数判定算法分析.教学管理[J].2001.12，75.

[ 4 ]赵改换.关于正整数数列中素数的分布规律[J].洛阳师专学报.2000，19（2），33-35.