施承忠素数大筛法基础理论

小草

施承忠素数大筛法基础理论

令
[A1]=[1]=1;[B1]=[2]=1
[A2]=[3,4]=2;[B2]=[5,6]=2
[A3]=[7,8,9]=3;[B3]=[10,11,12]=3
.
.
.
[An]=[a1,a2,a3,...,an]=n;[Bn]=[b1,b2,b3,...,bn]=n

则
(2∑(1,n)n)-n=n^2

令p是素数，g是合数.gn是pn的合数，其中pn是gn中最小的因子.
把[An],[Bn]中的素数移人[pn]中，把[An],[Bn]中的合数移人[gn]中.

则
[A1]=[1]=1;[B1]=[2]=1
[A2]=[3,4]=2;[B2]=[5,6]=2
[A3]=[7,8,9]=3;[B3]=[10,11,12]=3
.
.
.
[An]=[a1,a2,a3,...,an]=n;[Bn]=[b1,b2,b3,...,bn]=n

变成
[A1]=[1]=1;[B1]=[2]=1
[p1]=[3,5]=2;[g1]=[4,6]=2
[p2]=[7,11,13]=3;[g2]=[9,15,21]=3
.
.
.
[pn]=[pt+1,pt+2,...,pt+n]=n;[gn]=[gs+1,gs+2,...,gs+n]=n

则
(1+∑(1,t)pt)+(∑(1,s1)gs1)+(2∑(1,s2)gs2)+1=n^2

令
(1+∑(1,t)pt)=π(p^2)
(∑(1,s1)gs1)+(2∑(1,s2)gs2)=G(p^2)
则
π(p^2)+G(p^2)+1=p^2

由于素数分散在An,Bn中不是匀等的
则
π(p^2)≈(1+∑(1,t)pt)

因为素数愈来愈稀素数的集合[pn]也愈来愈稀，相反合数愈来愈密，合数的集合[gn]也愈来愈密.

实例：
[A1]=[1];[B1]=[2]=1.
[p1]=[3,5]=2.
π(2^2)≈(1+∑(1,1)pk)=3.
实际
[A1]=[1];[B1]=[2]=1.
[p1]=[3]=1;[g1]=[4]=1.
其中5>4,[g1]=[4]=1不在计算范围内.
实际
π(2^2)=2，G(2^2)=1，[A1]=[1]=1.
【】
[A1]=[1]=1;[B1]=[2]=1.
[p1]=[3,5]=2;[g1]=[4,6]=2.
[p2]=[7,11,13]=3.
π(3^2)≈(1+∑(1,2)pk)=6.
实际
[A1]=[1];[B1]=[2]=1.
[p1]=[3,5]=2;[g1]=[4,6]=2.
[p2]=[7]=1;[g2]=[9]=1.
[g1]=[8]=1.
其中11,13>9,[g1]=[8]=1,[g2]=[9]=1不在计算范围内.
实际π(3^2)=4，G(3^2)=4，[A1]=[1]=1.
【】
[A1]=[1]=1;[B1]=[2]=1.
[p1]=[3,5]=2;[g1]=[4,6]=2.
[p2]=[7,11,13]=3;[g2]=[9,15,21]=3.
[g1]=[8,10,12,14]=4;[g1]=[16,18,20,22]=4.
[p3]=[17,19,23,29,31]=5.
π(5^2)≈(1+∑(1,3)pk)=11.
实际
[A1]=[1];[B1]=[2]=1.
[p1]=[3,5]=2;[g1]=[4,6]=2.
[p2]=[7,11,13]=3;[g2]=[9,15,21]=3.
[g1]=[8,10,12,14]=4;[g1]=[16,18,20,22]=4.
[p3]=[17,19,23]=3;[g3]=[25]=1.
[g1]=[24]=1.
其中29,31>25,[g1]=[24]=1,[g3]=[25]=1不在计算范围内.
实际π(5^2)=9，G(5^2)=15，[A1]=[1]=1.