|
|
楼主 |
发表于 2021-12-5 09:20
|
显示全部楼层
本帖最后由 cuikun-186 于 2021-12-5 10:45 编辑
双筛法的步骤：
首先给出：偶数N=2n+4，建立如下互逆数列：
首项为1，末项为N-1,公差为2的等差数列A
再给出首项为N-1,末项为1，公差为-2的等差数列B
显然N=A+B
根据埃氏筛法获得奇素数集合P：
｛3，5，…，Pr｝,Pr<N^1/2
为了获得偶数N的表法数，按照双筛法进行分步操作：
第1步：将互逆数列用3双筛后得到真实剩余比m1
第2步：将余下的互逆数列用5双筛后得到真实剩余比m2
第3步：将余下的互逆数列用7双筛后得到真实剩余比m3
…
依次类推到：
第r步：将余下的互逆数列用Pr双筛后得到真实剩余比mr
这样就完成了对偶数N的求双筛法表法数，根据乘法原理有：
r2(N)=（N/2）*m1*m2*m3*…*mr
即r2(N)=(N/2)∏mr
根据素数定理我们可以综合上面的双筛法:
r2(N)至少有N/(lnN)^2个，那就是对共轭的AB数列：
第一步：
不超过偶数N的奇素数至少有N/lnN个
第二步：
再次运用1/lnN筛选这至少有N/lnN个奇素数
根据乘法原理：
则r2(N)≥N/(lnN)^2≥[N/(lnN)^2]
例如：70
见下2个图片 |
本帖子中包含更多资源
您需要 登录 才可以下载或查看，没有帐号？注册
x
|
IP卡
狗仔卡
显身卡