要达到双筛的目的,运用共轭数列是最简单的:
对于共轭互逆数列A、B:
A:{1,3,5,7,9,……,(N-1)}
B:{(N-1),……,9,7,5,3,1}
显然N=A+B
根据埃氏筛法获得奇素数集合{Pr}:
{1,3,5,…,Pr},Pr<√N
例如我们要双筛偶数70,则:
对于共轭互逆数列A、B:
A:{1,3,5,7,9,……,69}
B:{69,……,9,7,5,3,1}
显然N=A+B,其中有35个奇数对。
根据埃氏筛法获得奇素数集合{Pr}:
{1,3,5,7},7<√70
例如:
[√70]=8,{Pr}={1,3,5,7},
3|/70,首先这35个奇数用3双筛后得到剩余13个奇数,则其真实剩余比:m1=13/35
5|70, 剩余的13个奇数再用5双筛剩余10个奇数,则其真实剩余比:m2=10/13
7|70, 剩余的10个奇数再用7双筛剩余10个奇数,则其真实剩余比:m3=10/10
根据真值公式得:
r2(70)
=(70/2)*m1*m2*m3
=35*13/35*10/13*10/10
=10
r2(70)=10
这是真值 |