给大家彻底讲透埃氏双筛法:
设奇素数Pr<N^1/2,那么有{Pr}奇素数集合,在任何大偶数N=2n≥10中,根据埃氏双筛法:去掉奇素数3的倍数后,剩余a1个奇数,
那么有3的真实剩余比:
m1=a1/n;
a1个奇数中再去掉5的倍数后剩余a2个奇数,那么有5的真实剩余比m2=a2/a1;
a2个奇数中去掉7的倍数后剩余a3个奇数,那么7的真实剩余比m3=a3/a2;依次进行双筛至P(r-1)剩余奇数为a(r-1)则P(r-1)的真实剩余比为:
a(r-1)/a(r-2);最后止于Pr
双筛后的剩余奇数ar,那么Pr的真实剩余比为:
mr=ar/a(r-1)
这里的奇素数p也可能提前终止双筛,那么有p至Pr的素数的真实剩余比都是1。
那么把这些结果代入真值计算公式有:
r2(N)=
n*a1/n*a2/a1*a3/a2*…*
ar/a(r-1)
=ar
即:r2(N)=ar
末筛素数Pr的真实剩余比mr≥m1>0,
有且仅有4种情况:
【1】mr=(1-2/Pr),m1=(1-2/3)
因为1-2/Pr≥1-2/3>0
所以mr≥m1>0
【2】mr=1-1/Pr,m1=1-1/3
因为1-1/Pr≥1-1/3>0
所以mr≥m1>0
【3】mr=(1-2/3Pr),m1=(1-1/3)
1-2/3Pr>1-1/3
所以mr>m1>0
【4】mr=(1-1/3Pr),m1=(1-2/3)
(1-1/3Pr)>(1-2/3)
所以mr>m1>0
以上4种情况穷尽所有情形,共同的结论是:mr≥m1>0,
进而根据崔坤真值公式:
r2(N)=(N/2)∏mr
获得 r2(N)≥1的结论。
还有一个方面可以说明:
【1】渐近剩余比h=1-2/p,表示不能整除偶数的奇素数在双筛时的渐近估计剩余比。
【2】能够整除偶数的奇素数在双筛时的剩余比z=1-1/p
【3】真实剩余比m是奇素数双筛时的真实剩余与被选奇数总个数的比。
【4】它们之间的关系:
1:m>h或者m<h,即m≠h
2:m=z
【5】m≠0,因为奇素数≠偶数,或者奇素数的积≠偶数。
从而获得:
获得 r2(N)≥1的结论。
当然要排除N-1是素数的(N-1,1)和(1,N-1)这2个数对
即r2(N)=ar≥1
或者r2(N)=ar-2>1