数学中国

标题: 求素单筛、求哥双筛误差 [打印本页]

作者: yangchuanju 时间: 2026-10-30 06:14
标题: 求素单筛、求哥双筛误差
求素单筛误差
给定一个正整数n，为求n内素数个数，可用埃氏筛法，分别用素数2,3,5,7……直至√n内最大素数p依次删除2,3,5,7……p的倍数数，但需保留2,3,5,7……p不被删除；
在筛余数中还有一个“孤岛1”。
为计算筛余数，人们总结出一个连乘积计算式n*∏(1-1/p)，须知该连乘积计算式的计算值不等于要求的素数个数；
其中的“孤岛1”保留在计算值中，素数2,3,5,7……p均不在计算值中，除此以外还有一个不整除误差。

例1：求9--24以内素数个数
正整数n n*1/2*2/3 素数筛余连乘-素数连乘-筛余综合误差
9 3.0000 4 3 -1.0000 0.0000 0.0000
10 3.3333 4 3 -0.6667 0.3333 0.3333
11 3.6667 5 4 -1.3333 -0.3333 -0.3333
12 4.0000 5 4 -1.0000 0.0000 0.0000
13 4.3333 6 5 -1.6667 -0.6667 -0.6667
14 4.6667 6 5 -1.3333 -0.3333 -0.3333
15 5.0000 6 5 -1.0000 0.0000 0.0000
16 5.3333 6 5 -0.6667 0.3333 0.3333
17 5.6667 7 6 -1.3333 -0.3333 -0.3333
18 6.0000 7 6 -1.0000 0.0000 0.0000
19 6.3333 8 7 -1.6667 -0.6667 -0.6667
20 6.6667 8 7 -1.3333 -0.3333 -0.3333
21 7.0000 8 7 -1.0000 0.0000 0.0000
22 7.3333 8 7 -0.6667 0.3333 0.3333
23 7.6667 9 8 -1.3333 -0.3333 -0.3333
24 8.0000 9 8 -1.0000 0.0000 0.0000
计算值中加上被筛掉的2和3，减去孤岛1，综合误差见表最后1列。
连乘-筛余之差每3个连续整数中有一个0，其余两数的“连乘-筛余”不固定；
但若只考察偶数10,12,14……24的“连乘-筛余”和综合误差分别是0.3333，0，-0.3333，0.3333，0，-0.3333，0.3333，0；三个连续偶数一个循环节。
（为使表格版面整齐，对于整数0,3,4,5,6,7,8均取3位小数，莫见怪！）

作者: yangchuanju 时间: 2026-10-30 06:14
例2：求25--48以内素数个数
正整数n n*1/2*2/3*4/5 素数筛余连乘-素数连乘-筛余综合误差
25 6.6667 9 7 -2.3333 -0.3333 -0.3333
26 6.9333 9 7 -2.0667 -0.0667 -0.0667
27 7.2000 9 7 -1.8000 0.2000 0.2000
28 7.4667 9 7 -1.5333 0.4667 0.4667
29 7.7333 10 8 -2.2667 -0.2667 -0.2667
30 8.0000 10 8 -2.0000 0.0000 0.0000
31 8.2667 11 9 -2.7333 -0.7333 -0.7333
32 8.5333 11 9 -2.4667 -0.4667 -0.4667
33 8.8000 11 9 -2.2000 -0.2000 -0.2000
34 9.0667 11 9 -1.9333 0.0667 0.0667
35 9.3333 11 9 -1.6667 0.3333 0.3333
36 9.6000 11 9 -1.4000 0.6000 0.6000
37 9.8667 12 10 -2.1333 -0.1333 -0.1333
38 10.1333 12 10 -1.8667 0.1333 0.1333
39 10.4000 12 10 -1.6000 0.4000 0.4000
40 10.6667 12 10 -1.3333 0.6667 0.6667
41 10.9333 13 11 -2.0667 -0.0667 -0.0667
42 11.2000 13 11 -1.8000 0.2000 0.2000
43 11.4667 14 12 -2.5333 -0.5333 -0.5333
44 11.7333 14 12 -2.2667 -0.2667 -0.2667
45 12.0000 14 12 -2.0000 0.0000 0.0000
46 12.2667 14 12 -1.7333 0.2667 0.2667
47 12.5333 15 13 -2.4667 -0.4667 -0.4667
48 12.8000 15 13 -2.2000 -0.2000 -0.2000
计算值中加上被筛掉的2,3和5，减去1，综合误差见表最后1列。
只考察偶数26,28,30……48的综合误差分别是-0.0667，0.4667，0，-0.4667，0.0667，0.6，0.1333，0.6667，0.2，-0.2667，0.2667，-0.2；
综合误差规律一时难寻。
实际上要找规律需从筛余、连乘-筛余中找，30个连续整数才构成一个循环节，本例整数个数不够30。

作者: yangchuanju 时间: 2026-10-30 06:16
扩大偶数范围至10--26--48--60，可以发现综合误差15个偶数一个循环节（10--40，12--42，14--44，16--46或18--48；
但20--50，22-52，24--54，26--56，28-58，30--60中大于等于50的综合误差要减去1才能成立误差循环节，可能是偶数50--60要用素数7筛分才行！
另从筛余、连乘-筛余中找，15个连续偶数构成一个循环节，连乘-筛余循环出现，且一个循环节中差值前后反对称。
例3：求10--60各个偶数以内素数个数
正整数n n*1/2*2/3*4/5 素数筛余连乘-素数连乘-筛余综合误差
10 2.6667 4 2 -1.3333 0.6667 0.6667
12 3.2000 5 3 -1.8000 0.2000 0.2000
14 3.7333 6 4 -2.2667 -0.2667 -0.2667
16 4.2667 6 4 -1.7333 0.2667 0.2667
18 4.8000 7 5 -2.2000 -0.2000 -0.2000
20 5.3333 8 6 -2.6667 -0.6667 -0.6667
22 5.8667 8 6 -2.1333 -0.1333 -0.1333
24 6.4000 9 7 -2.6000 -0.6000 -0.6000
26 6.9333 9 7 -2.0667 -0.0667 -0.0667
28 7.4667 9 7 -1.5333 0.4667 0.4667
30 8.0000 10 8 -2.0000 0.0000 0.0000
32 8.5333 11 9 -2.4667 -0.4667 -0.4667
34 9.0667 11 9 -1.9333 0.0667 0.0667
36 9.6000 11 9 -1.4000 0.6000 0.6000
38 10.1333 12 10 -1.8667 0.1333 0.1333
40 10.6667 12 10 -1.3333 0.6667 0.6667
42 11.2000 13 11 -1.8000 0.2000 0.2000
44 11.7333 14 12 -2.2667 -0.2667 -0.2667
46 12.2667 14 12 -1.7333 0.2667 0.2667
48 12.8000 15 13 -2.2000 -0.2000 -0.2000
50 13.3333 15 14 -1.6667 -0.6667 0.3333
52 13.8667 15 14 -1.1333 -0.1333 0.8667
54 14.4000 16 15 -1.6000 -0.6000 0.4000
56 14.9333 16 15 -1.0667 -0.0667 0.9333
58 15.4667 16 15 -0.5333 0.4667 1.4667
60 16.0000 17 16 -1.0000 0.0000 1.0000

作者: yangchuanju 时间: 2026-10-30 06:17
正整数n以内有多少个素数？
先用素数2筛一下，若n是偶数，筛掉一半，剩余一半，无误差；若n是奇数，筛掉一半少一点（0.5），剩余一半多一点（0.5）；
以下只考虑n是偶数的情况。
接着用素数3筛分，筛掉[n/2*1/3]，（[***]表示向下取整），筛余n/2-[n/2*1/3]，连乘积-剩余等于±0.3333或0；
2筛后单用素数5筛分，筛掉[n/2*1/5]，（[***]表示向下取整），筛余n/2-[n/2*1/5]，连乘积-剩余等于±0.2，±0.4或0；
2 3筛后再用素数5筛分，连乘积-剩余15个偶数一循环。

不考虑取整，只按倍数含量的筛除、筛余计算，
2 3筛除量是n/2*1/3，筛余量是n/2-n/2*1/3；
接着用素数5筛，筛除量是(n/2-n/2*1/3)*1/5，筛余量是n/2-n/2*1/3-(n/2-n/2*1/3)*1/5=n/2*(1-1/3)-n/2*(1/5-1/15)=n/2*(1-1/3-1/5+1/15)；
继续用素数7筛，筛除量是n/2*(1-1/3-1/5+1/15)*1/7，筛余量是n/2*(1-1/3-1/5+1/15)-n/2*(1-1/3-1/5+1/15)*1/7=n/2*(1-1/3-1/5+1/15)-n/2*(1/7-1/21-1/35+1/105)=n/2*(1-1/3-1/5-1/7+1/15+1/21+1/35-1/105)；
该计算式值等于n/2*0.457142857，与n/2*2/3*4/5*6/7=n/2*0.457142857完全相等，连乘积计算式要比减减加加式简单的多。

按减减加加式算一算11筛，筛除量是n/2*(1-1/3-1/5-1/7+1/15+1/21+1/35-1/105)*1/11，
筛余量是n/2*(1-1/3-1/5-1/7+1/15+1/21+1/35-1/105)-n/2*(1-1/3-1/5-1/7+1/15+1/21+1/35-1/105)*1/11
=n/2*(1-1/3-1/5-1/7+1/15+1/21+1/35-1/105)-n/2*(1/11-1/33-1/55-1/77+1/165+1/231+1/385-1/1155)=n/2*(1-1/3-1/5-1/7-1/11+1/15+1/21+1/35+1/33+1/55+1/77-1/105-1/165-1/231-1/385+1/1155)=n/2*0.415584416，
连乘积计算式是n/2*2/3*4/5*6/7*10/11=n/2*0.415584416，完全相等。

不考虑取整，只按倍数含量的筛除、筛余计算，算不出误差。

作者: yangchuanju 时间: 2026-10-30 06:18
求哥双筛误差
给定一个正偶数n，为求n内哥德巴赫猜想分拆素数对数，可列两列正整数1,3,5,……,n-3,n-1和n-1,n-3,n-5,……,3,1，两两对齐，分别用素数2,3,5,7……直至√n内最大素数p依次删除两列正整数中的2,3,5,7……p的倍数数，俗称双筛；
在筛余数对中有时残留有非素数对1+(n-1)和(n-1)，但哥猜素数对中的小素数对均被筛除。
为计算筛余素数对，人们总结出一个连乘积计算式n/2*∏(1-2/p)*∏(p-2)/(p-1)，式中第一个连乘积中的p取尽√n内所有奇素数，第二个连乘积中的p仅取√n内能够整除n的奇素数。
须知该连乘积计算式的计算值不等于要求的素数对数；存在三种误差。

例4：求10--24各个偶数的哥猜素数对数
偶数连乘积双哥筛余连乘-双哥连乘-筛余
10 1.6667 3 1 -1.3333 0.6667
12 4.0000 2 4 2.0000 0.0000
14 2.3333 3 3 -0.6667 -0.6667
16 2.6667 4 2 -1.3333 0.6667
18 6.0000 4 6 2.0000 0.0000
20 3.3333 4 4 -0.6667 -0.6667
22 3.6667 5 3 -1.3333 0.6667
24 8.0000 6 8 2.0000 0.0000
表中连乘积等于n/2*1/3或n/2*2/3，连乘-双哥构成比较复杂，但连乘-筛余已经呈现出3偶一循环的规律——0，-0.6667，0.6667；0，-0.6667，0.6667；……

作者: yangchuanju 时间: 2026-10-30 06:19
例5：求10--60各个偶数的哥猜素数对数
偶数连乘积双哥筛余连乘-双哥连乘-筛余
10 1.3333 3 0 -1.6667 1.3333
12 2.4000 2 2 0.4000 0.4000
14 1.4000 3 3 -1.6000 -1.6000
16 1.6000 4 0 -2.4000 1.6000
18 3.6000 4 4 -0.4000 -0.4000
20 2.6667 4 4 -1.3333 -1.3333
22 2.2000 5 1 -2.8000 1.2000
24 4.8000 6 6 -1.2000 -1.2000
26 2.6000 5 3 -2.4000 -0.4000
28 2.8000 4 2 -1.2000 0.8000
30 8.0000 6 8 2.0000 0.0000
32 3.2000 4 4 -0.8000 -0.8000
34 3.4000 7 3 -3.6000 0.4000
36 7.2000 8 6 -0.8000 1.2000
38 3.8000 3 5 0.8000 -1.2000
40 5.3333 6 4 -0.6667 1.3333
42 8.4000 8 8 0.4000 0.4000
44 4.4000 6 6 -1.6000 -1.6000
46 4.6000 7 3 -2.4000 1.6000
48 9.6000 10 10 -0.4000 -0.4000
50 6.6667 8 8 -1.3333 -1.3333
52 5.2000 6 4 -0.8000 1.2000
54 10.8000 10 12 0.8000 -1.2000
56 5.6000 6 6 -0.4000 -0.4000
58 5.8000 7 5 -1.2000 0.8000
60 16.0000 12 16 4.0000 0.0000
表中连乘积等于n/2*1/3或n/2*2/3再乘以3/5或4/5，连乘-双哥构成比较复杂，但连乘-筛余已经呈现出15偶一循环的规律，且前后反对称；偶数30,60误差为0；偶数14,16,44,46的误差最大为±1.6。

作者: cuikun-186 时间: 2026-10-30 07:11
本帖最后由 cuikun-186 于 2026-10-30 07:31 编辑

杨老师你好，

无论单筛还是双筛，都有如下例子：

【1】D(N)=[(π(N)^2/N]向下取整

【2】r2(N)=[(π(N)^2/N]向下取整

π(N)是包含1的所有素数的个数。

特别是128这个偶数有8对素数对，

r2(128)=8.

π埃氏(128)=π崔(128)=32，

r2(128)≥[32*32/128]=8

不超过128的素数有：

1、2、3、5、7、11、13、17、19、

23、29、31、37、41、43、47、53、

59、61、67、71、73、79、83、89、

97、101、103、107、109、113、127。

共 32个。

作者: cuikun-186 时间: 2026-10-30 07:25
D(100)=[26*26/100]=6

作者: cuikun-186 时间: 2026-10-30 07:33

特别是128这个偶数有8对素数对，

r2(128)=8.

π埃氏(128)=π崔(128)=32，

r2(128)≥[32*32/128]=8

不超过128的素数有：

1、2、3、5、7、11、13、17、19、

23、29、31、37、41、43、47、53、

59、61、67、71、73、79、83、89、

97、101、103、107、109、113、127。

共 32个。

这个实际数据彻底否定了欧拉的谬论！

欢迎光临数学中国 (http://www.mathchina.com/bbs/)