双筛法在计算中的应用

《双筛法在计算中的应用》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、双筛法在计算中的应用作者姓名：弯国强作者地址：漯河市舞阳县莲花镇第二初级中学E-mail：632158@163.com摘要：本文运用双筛法总结了准确的孪生素数，2a生素数，以及哥德巴赫素数对的公式。并结合容斥定理证明了孪生素数，2a生素数，以及哥德巴赫素数对的公式的成立。从而结束了孪生素数，2a生素数，以及哥德巴赫素数对的公式只有近似公式而没有准确公式的历史，为进一步研究素数分布规律，彻底解决孪生素数猜想和哥德巴赫猜想提供了有力的理论依据。关键词：素数、双筛法、孪生素数公式、2a生素数公式、哥德巴赫素数对的公式中图分类号：O156.1双筛法是在埃拉托色尼斯基础上，进行扩展得到的一

2、种筛法。这种筛法的基本特征是首先在自然数中筛去合数，得到素数；然后再根据需要，依据一定的条件筛去相应的不适合条件的素数，剩余的数就是需要留下的数。双筛法可以成功地应用于孪生素数，2a生素数，以及哥德巴赫素数对的计算问题。若自然数p与p+2同时不能被不大于p+2的任何素数整除，则p与p+2是一对素数，称为孪生素数。分析下面相差为2的数组（１，３）；（２，４）；…（k，k+2）；…（ｎ，ｎ＋２）(１≤k≤n)若p,,,p""p为连续素数，不超过n的前部素数的个数为mn=π()+212m根据孪生素数的定义，我们可以得到在上面n个数组中筛去xp≡0mod，即是pii倍数再筛去xp+≡20

3、mod，即是xp≡−2mod(i=1,2""m)，则余下的数ii组（k，k+2）中，k和k+2都不是前m个素数的倍数，根据素数的判定定理，余下的数组全为素数且相差为2，即为后部孪生素数。然后在前部素数中找出孪生素数，就可以得到前部孪生素数。那么不超过n的孪生素数的个数就等于前部孪生素数的个数加上后部孪生素数的个数。也可以这样理解，首先在上面n个数组中筛去合数，数组中第一个数剩下1和质数，接着在质数中再筛去xp+≡20mod，即是xp≡−2mod(im=1,2"")，则ii余下的数组（k，k+2）中，k和k+2都不是前m个素数的倍数，根据素数的判定定理，余下的数组全为素数且相差为2

4、，即为后部孪生素数。然后在前部素数中找出孪生素数，就可以得到前部孪生素数。那么不超过n的孪生素数的个数就等于前部孪生素数的个数加上后部孪生素数的个数。根据以上分析，可以求出不超过正整数n的一切孪生素数，具体方法是：首先写出1，2，3，…………n—1，n。不超过n+2的前部素数为p,,,pp""12m在自然数中筛去合数1、划去2的倍数。2、划去3的倍数。……………………………………m+1、划去p的倍数。m做到这里，剩下的数就是不超过n的后部素数和1。在素数中筛去非孪生素数再分别划去3k－２;5k－２……kp−2就可以得到不超过n的后部孪生素数。m然后在前部素数中找出孪生素数，就可以

5、得到前部孪生素数。那么不超过n的孪生素数的个数就等于前部孪生素数的个数加上后部孪生素数的个数。仿照素数公式可得出类似的孪生素数计算公式设：xi≡02或-(modpi)⎧x≡02或-(modp)⎪iji⎨⎪x≡02或-(modp)⎩ijj"""""""⎧x≡0(modp)12"i1⎪⎪⎪x12"i≡02或-(modp2)⎨⎪""⎪⎪x≡02或-(modp)⎩12"ii()im=1,2""x,,xx""是同余方程组的解，这些解取解的绝对值不大于模的负值。iji12"i孪生素数计算公式：Tn()表示不超过n的孪生素数的个数。⎡⎤mm⎡⎤nx−−⎡⎤nx−jim⎢⎥nx=−⎢⎥ii+⎢⎥

6、++−⎢⎥12"++Tnn()∑∑""()12mTn()ij=<2⎣⎦ppiji⎢⎥⎣⎦pi⎢⎥⎢⎥∏pi⎣⎦i=1mn=+π()2为n+2的前部素数的个数，Tn(+2)为前部素数中能构成孪生素数的素数个数，即前部孪生素数的个数。⎡⎤mm⎡⎤nx−−⎡⎤nx−jim⎢nx⎥−++⎢⎥ii⎢⎥+−⎢12"⎥n∑∑""()1m为后部孪生素数的个数。ij=<2⎣⎦ppiji⎢⎥⎣⎦pi⎢⎥⎢∏pi⎥⎣i=1⎦⎧x≡0(modp)⎪iji设yi表示xi中去掉xi≡0(modpi)的解；设yij表示xij中去掉⎨的解；⎪x≡0(modp)⎩ijj…………………………………………………………

7、……………………………………………⎧x≡0(modp)12"i1⎪⎪⎪x12"i≡0(modp2)⎨y12"i表示x12"i中去掉⎪""的解。那么公式又可以改写为：⎪⎪x≡0(modp)⎩12"ii()im=1,2""⎡⎤mm⎡⎤ny−−⎡⎤ny−jim⎢⎥ny=−⎢⎥ii+⎢⎥++−⎢⎥12"+++−Tn()π()n∑∑""()12mTn()1mij=<2⎣⎦ppiji⎢⎥⎣⎦pi⎢⎥⎢⎥∏pi⎣⎦i=1当不超过n的素数的个数已知时qTn()=+∑⎡⎤⎣⎦ππ(pkk++112