双筛法告诉我们（1+1）表法数r2(N)≥1

cuikun-186

双筛法告诉我们（1+1）表法数r2(N)≥1

原创：崔坤

众所周知的π（N）是计数函数，素数定理：π（N）～N/lnN

这就告诉人们要获得（1+1）表法数：

第一步：【崔坤在这里定义1是奇素数】

首先要获得N内的奇素数个数要用筛子1/lnN获取，即至少有N/lnN个奇素数

第二步：

要获得N内的奇素数对个数r2(N),继续用筛子1/lnN对N/lnN个奇素数进行再次筛选。

根据乘法原理，

那么：r2(N)至少有（N/lnN)*(1/lnN)个

即r2(N)≥N/（lnN）^2

例如：

N=100,

第一步：N/lnN=100/ln100取整=21

第二步：r2(N)≥N/（lnN）^2

r2(100)≥100/（ln100）^2=4.715，取整=4

则：r2(100)≥4

实际上r2(100)=12 ，π（100）=25

创作于2021年10月1日9点28分于青岛即墨

cuikun-186

r2(N)至少有（N/lnN)*(1/lnN)个

即r2(N)≥N/（lnN）^2

例如：

N=10^5,

第一步：N/lnN=10^5/ln100^5取整=8685

第二步：r2(N)≥N/（lnN）^2

r2(10^5)≥10^5/（ln10^5）^2取整=754

则：r2(10^5)≥754

实际上r2(10^5)=1620 ，π（10^5）=9592

cuikun-186

首先给出：偶数N=2n，建立如下互逆数列：

首项为1，末项为N-1,公差为2的等差数列A

再给出首项为N-1,末项为1，公差为-2的等差数列B

显然N=A+B

根据埃氏筛法获得奇素数集合P：

｛1，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


双筛法的mr>0

证明：(反证法)

众所周知，

按照双筛法的第r步就是用小于N^1/2的奇素数Pr双筛有前一个素数P（r-1）双筛后留下的奇数，

而有且仅有这些奇数都是Pr的倍数才能被Pr筛掉，

即至少在（N/2，N）之间没有任何素数。

这个结论显然与素数的性质定理【在（N/2，N）之间至少有一个素数】矛盾。

故mr>0

cuikun-186

例如：
[√70]=8，｛Pr｝={3,5,7},
3|/70，m1=13/35
5|70, m2=10/13
7|70, m3=10/10
根据真值公式得：
r2(70)
=(70/2)*m1*m2*m3
=35*13/35/10/13*10/10
=10
r2(70)=10为真
[√34]=5，｛Pr｝={3,5},
3|/34，m1=7/17
5|/34, 5的倍数已被3全部筛掉，
即5的倍数没有剩余，但剩余比m2=7/7=1
根据真值公式得：
r2(34)
=(34/2)m1*m2=17*1*7/17=7
r2(34)=7为真
[√210]=14，
｛Pr｝={3,5,7，11，13},
3|210,m1=2/3
5|210,m2=4/5
7|210，m3=6/7
11|/210,m4=5/6
13|/210,m5=19/20
根据真值公式得：
r2(210)
=(210/2)*m1*m2*m3*m4*m5
=105*2/3*4/5*6/7*5/6*19/20
=38
r2(210)=38为真

cuikun-186

r2(N)至少有（N/lnN)*(1/lnN)个

即r2(N)≥N/（lnN）^2

例如：

N=80

第一步：N/lnN=80/ln80取整=18

第二步：r2(N)≥N/（lnN）^2

r2(80)≥80/（ln80）^2取整=4

则：r2(80)≥4

实际上r2(80)=10 ，π（80）=22

cuikun-186

双筛法告诉我们（1+1）表法数r2(N)≥1

原创：崔坤

众所周知的π（N）是计数函数，素数定理：π（N）～N/lnN

这就告诉人们要获得（1+1）表法数：

第一步：【崔坤在这里定义1是奇素数】

首先要获得N内的奇素数个数要用筛子1/lnN获取，即至少有N/lnN个奇素数

第二步：

要获得N内的奇素数对个数r2(N),继续用筛子1/lnN对N/lnN个奇素数进行再次筛选。

根据乘法原理，

那么：r2(N)至少有（N/lnN)*(1/lnN)个

即r2(N)≥N/（lnN）^2

例如：

N=100,

第一步：N/lnN=100/ln100取整=21

第二步：r2(N)≥N/（lnN）^2

r2(100)≥100/（ln100）^2=4.715，取整=4

则：r2(100)≥4

实际上r2(100)=12 ，π（100）=25

创作于2021年10月1日9点28分于青岛即墨

cuikun-186

1是素数，2011年有新书公布：