何为筛子？

cuikun-186 · 发表于 2022-1-6 19:36

何为筛子？

cuikun-186 · 发表于 2022-1-6 19:47

本帖最后由 cuikun-186 于 2022-1-6 19:57 编辑

我们以70为例，我们的筛法是双筛法。

[70^1/2]=8，8以内的素数1，3，5，7

第一步用3双筛得真实剩余比m1=13/35，

第二步用5双筛得到真实剩余比m2=10/13，

第三步用7双筛得到真实剩余比m3=10/10

根据乘法原理得到:

r2(70)=(70/2)*m1*m2*m3=35*13/35*10/13*10/10=10

r2(N)=(N/2)*∏mr，

显然：∏mr=r2(N)/N/2就是偶数N的筛子：

∏mr（70）=r2(70)/70/2=10/70/2=2/7

显然2/7=0.2857…>1/ln70=0.235377…

cuikun-186 · 发表于 2022-1-6 19:49

本帖最后由 cuikun-186 于 2022-1-6 20:16 编辑

如果我们结合素数定理就可以这样理解：

首先众所周知，

根据乘法原理N中至少有[N/lnN]个素数，

也就是说：N中的素数可以至少用1/lnN筛选，

那么N中至少有[N/lnN]个素数，

结合双筛法，这是对互为共轭的等差数列A数列筛得到的素数个数，

同时也是共轭数列AB中至少有的素数个数。

以上只是对A数列筛，即是第一步，

还有B数列没有筛，由于B数列与A数列是互逆数列，

那么其筛子也是1/lnN,再对第一步得来的[N/lnN]个素数进行筛，

这样根据乘法原理，

N中至少有:[N/lnN]*(1/lnN)=[N/(lnN)^2]个素数

根据双筛法原理这就得到了N中（1+1）表法数至少有[N/(lnN)^2]个

cuikun-186 · 发表于 2022-1-6 19:51

如果我们结合素数定理就可以这样理解：

首先众所周知，

根据乘法原理N中至少有[N/lnN]个素数，

也就是说：N中的素数可以至少用1/lnN筛选，

那么N中至少有[N/lnN]个素数，

结合双筛法，这是对互为共轭的等差数列A数列筛得到的素数个数，

同时也是共轭数列AB中至少有的素数个数。

以上只是对A数列筛，即是第一步，

还有B数列没有筛，由于B数列与A数列是互逆数列，

那么其筛子也是1/lnN,再对第一步得来的[N/lnN]个素数进行筛，

这样根据乘法原理，

N中至少有:[N/lnN]*lnN=[N/(lnN)^2]个素数

根据双筛法原理这就得到了N中（1+1）表法数至少有[N/(lnN)^2]个

cuikun-186 · 发表于 2022-1-7 06:30

本帖最后由 cuikun-186 于 2022-1-7 08:06 编辑

再看100，
100^1/2=10，Pr:1,3,5,7
m1=16/50
m2=14/16
m3=12/14
r2(100)=(100/2)*∏mr＝50*16/50*14/16*12/14=12
∏mr＝r2（100）/100/2=12/50=0.24
偶数100的筛子是0.24
而有素数定理可知100的筛子至少是1/ln100=0.2171…
显然0.24>1/ln100

cuikun-186 · 发表于 2022-1-7 08:35

本帖最后由 cuikun-186 于 2022-1-7 08:43 编辑

埃拉托斯特尼筛法，简称埃氏筛或爱氏筛，是一种由希腊数学家埃拉托斯特尼所提出的一种简单检定素数的算法。
要得到自然数N以内的全部素数，必须把不大于根号N的所有素数的倍数剔除，剩下的就是素数。
要得到自然数N以内的全部素数，必须把不大于N的所有素数的倍数剔除，剩下的就是素数。
给出要筛数值的范围，找出以内的素数。
先用2去筛，即把2留下，把2的倍数剔除掉；
再用下一个质数，也就是3筛，把3留下，把3的倍数剔除掉；
接下去用下一个质数5筛，把5留下，把5的倍数剔除掉；
........
不断重复下去......。
详细列出算法如下：
列出2以后的所有序列：
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
标出序列中的第一个素数，也就是2，序列变成：
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
将剩下序列中，划掉2的倍数，序列变成：
2 3 5 7 9 11 13 15 17 19 21 23 25
如果这个序列中最大数小于最后一个标出的素数的平方，那么剩下的序列中所有的数都是素数，否则回到第二步。
本例中，因为25大于2的平方，我们返回第二步：
剩下的序列中第一个素数是3，将主序列中3的倍数划掉，主序列变成：
2 3 5 7 11 13 17 19 23 25
我们得到的素数有：2，3
25仍然大于3的平方，所以我们还要返回第二步：
序列中第一个素数是5，同样将序列中5的倍数划掉，主序列成了：
2 3 5 7 11 13 17 19 23
我们得到的素数有：2，3，5 。
因为23小于5的平方，跳出循环.
结论：2到25之间的素数是：2 3 5 7 11 13 17 19 23。

cuikun-186 · 发表于 2022-1-8 05:19

埃氏筛法是伟大的筛法

cuikun-186 · 发表于 2022-1-9 08:36

古代数论中自然数不包括0

wangyangke · 发表于 2025-8-3 12:33

在数学论坛，包装和推销靠不住的东西————除cuikun-186外；因为，这样说得过去！————是愚蠢行为！

论坛上没有称得上靠得住的————除崔坤的哥猜证明外；因为，这样，行得通！————哥猜证明，却有些靠得住的二百五；鲁思顺是二百五中的突出代表，，，

		自动登录	找回密码
密码			注册

何为筛子？

点评