素数快速筛法及公式

素数快速筛法及公式

梅生林 安徽合肥 2012.07.12

摘要：在素数的研究中，总结出素数快速筛法及公式，在这个基础上扩展了素数的一些关系、性质。

关键词：素数快速筛法，素数通式，质数筛法公式 1.引言

素数（Prime Number）是指自然数中那些只能被1和本身整除的数，依次为2、3、5、7、11、13、17、19、23、29?。前人已证明：素数有无限多个。一直到现在人们判定、寻找素数的方法，还是古希腊的数学家艾拉托斯芬（Eratosthenes）提出过的筛式方法，简称“艾氏筛法”。即在任意有限自然数N以内判定素数时，先把N一个不漏的写下来，然后划掉根号N（

?）内所有素数的倍数，我们就能得到

N以内的全部素数。艾氏筛法判定素数的过程机械，也未能表示素数公式和一些性质。

关于寻找判定表示素数的方法公式，以前众多数学家进行了艰辛探索，也提出了很多关于素数的猜想和问题。欧拉(Euler)就提出二项式公式n2-n+41能生成一部分素数的数型公式，直到现在，素数研究中仍然还有许多未解问题。本文通过素数快速筛法及公式，总结出一些素数的新理论，使素数筛法及公式等都将是一次质变，将为素数研究抛砖引玉，也可能为数论增添上新的一页。

1

2. 素数的快速筛法原理及公式

当我们用艾氏筛法是要划掉每个合数，只2的倍数就差不多要划掉一半自然数，越往后面合数越多，而留下的素数越少。我们能不能利用数学原理、公式去掉大部分合数呢？答案是肯定的。 2.1 当我们想去掉第一个素数2的倍数时，我们可能会想到用：

2N+1 （N≥1）N为大于等于1的自然数，以下公式同上。 2.2 去掉2、3的倍数时，用2*3的倍数加上同为2、3互质的数：

6N±1

2.3 去掉2、3、5的倍数时，用2*3*5的倍数加上同为2、3、5互质的数：

30N±1， 30N±7， 30N±11， 30N±13， 2.4 去掉2、3、5、7的倍数时，同上的方法：

210N±1， 210N±11， 210N±13， 210N±17， 210N±19， 210N±23， 210N±29， 210N±31， 210N±37， 210N±41， 210N±43， 210N±47， 210N±53， 210N±59， 210N±61， 210N±67， 210N±71， 210N±73， 210N±79， 210N±83， 210N±89， 210N±97， 210N±101， 210N±103， 2.5 去掉2、3、5、7、11的倍数时，同上的方法：

2310N±1， 2310N±13， 2310N±17， 2310N±19， ? ?

2

2310N±1139， 2310N±1147， 2310N±1151， 2310N±1153， 我们可以一直做下去，就会去掉从前面开始的素数倍数，划掉的合数比例将越来越少。

2.6 将上面的方法归纳成一个动态的公式：

假设素数2、3、5、7、11 ? K，用P1、P2、P3、P4、P5? PK表示; N的取值范围：1 ≤ N ≤(P（K+1）-1)/2;

KPX是前式(P1P2P3*? *PK) *N加上互质的数生成的数; ! (P（K+1） *(P（K+1） ,?, KPX))是划掉P（K+1）的倍数。 素数动态的公式：

(P1P2P3?PK) *N + (-KPX ,?,-P（K+1） ,-1,1,P（K+1） ,?,KPX ) ! (P（K+1） *(P（K+1） ,?, KPX))

2.7 公式说明：

当6N±1的N的取值范围：1 ≤ N ≤(5-1)/2 可得到：5，7，11，13就满足了30N±互质数的要求。 当30N±1，30N±7，30N±11，30N±13的N的取值范围：1 ≤ N ≤(７-1)/2

可得到：17，19，23，29，31，37，41，43，47，49，53，59，61，67，71，73，77，79，83，89，91，97，101，103，

再用公式：! (P（K+1） *(P（K+1） ,?, KPX))去掉7的倍数：7*7=49，7*11=77，7*13=91就满足了210N±互质数的要求了。

用同上的方法就可以一直快速的筛选下去。

3

2.8 求N以内的全部素数方法：

我们要想得到N以内的全部素数，我们用上面的快速筛法,生成数到小于等于N为止，再用动态划去合数公式：

! (P（K+1） *(P（K+1） ,?, KPX))

只要素数P（K+1）后面的相连素数P（K+2?）满足： ! (P（K+2?） *(P（K+2?） ,?, KPX)) ≤N

一直去掉后面的相连素数的倍数，剩下的就素数了。

后面划去合数方法也同“艾氏筛法”一样，但是只要划掉占全部合数个数比例较小的后段大素数的倍数。

如求300以内素数，只要生成到210*1+89=299就可以， 生成时已经划去了30N±互质数内的7*7=49，7*11=77，7*13=91; 再划去210N±互质数至300内11、13、17的倍数： 11*11=121,11*13=143,11*17=187,11*19=209,11*23=253； 13*13=169，13*17=221，13*19=247，13*23=299； 17*17=289. 3．总结

用素数的阶乘积为模的倍数加上小于模并互质的数，来筛去模中素数的倍数。虽然素数的阶乘积是倍数式增长，但筛去整个自然数中的合数也是呈现倍数式减少，快速筛法中可以看出，前面2、3、5的倍数自动被筛去，后面的素数（假设PK）一直筛下去应划掉的个数可用公式求出：

（2-1）（3-1）（5-1）（7-1）?（P（K-1）-1）/2–1

4

例如：

7只要划掉3个：（2-1）（3-1）（5-1）/2-1； 11只划掉23个：（2-1）（3-1）（5-1）（7-1）/2-1； 13只划掉239个：2*4*6*10/2-1；

虽然越往后面筛去，大素数要划掉的个数增长也快，但是相对它的全部倍数的合数还是很小的一部分，又主要是在自然数中，前面小素数的倍合数，所占自然数中的比例将是绝对的多，从中也让我们看到了素数的美丽——自然界中的组成单元“互补不完全对称性”。

从前面的动态公式可以变换成多种公式，比如下面的一个公式： (P1P2P3?PK)(2N-1)/2+(-KPX ,?,-P（K+1） ,-1,1,P（K+1） ,?,KPX )*2n ! (P（K+1） *(P（K+1） ,?, KPX))

中2、3、5、7的倍数自动被筛去，11、13等后面的素数又可以少划掉一半以上合数，但要增加排序等运算。

最后我们从这些公式关系中，可以发现一些素数、合数以及自然数的一些规律，对解决一些素数、数论问题将会翻开新的一页。此致

欢迎交流讨论、留言共勉！

梅生林

Tel:13430930031

Email： 2574674176@QQ.COM ADDR:安徽合肥庐江县泥河镇八里村

5