素数计数公式全面拉丁化改写-小有改进-Meissel公式-梅塞尔-Lehmer公式-莱梅=勒梅尔-筛法三种形式-孟庆余公式(转载)
何冬州的百度空间Blog
本文的另一版本:http://hi.baidu.com/wsktuuytyh/blog/item/396a934ac679680208f7ef2c.html信息革命先驱者/数学电脑爱好者
注： wsktuuytyh 即何冬州 三字的五笔编码
|
|
|
|
素数计数公式全面拉丁化改写-小有改进-Meissel公式-梅塞尔-Lehmer公式-莱梅=勒梅尔-筛法三种形式-孟庆余公式
2012年06月13日 星期三6:17
本文标题：
素数计数公式全面拉丁化改写-小有改进-Meissel公式-梅塞尔-Lehmer公式-莱梅=勒梅尔-筛法三种形式-孟庆余公式
前言:
约在2002~2003年我在家闲呆了段时间,专心自学数论,矩阵论等资料,自己有些心得。
其中有一件小事,就是计算万以内的素数的个数.
当时自行推导几个公式,近日发现,与Legendre公式, Meissel公式一致,但没有Meissel公式这样简明.近日看到Meissel公式,与自己的想法一结合,发现可以简化Meissel公式.
而Lehmer公式,我当时有这样的思路,作了这样的计算,不过没有整理成公式.
此外,看到孟庆余先生的公式,觉得很奇特,竟然使用四舍五入,我还没有验证.
而王晓明素数计数公式,我在2003年的数学笔记中已经有这样的计算,但是,我并不觉得有什么特别,因为黎曼和欧拉等人比我走得老远.我当前试图精确控制误差,找到这个公式的小数部分的误差限,结果没有成功.网上盛传的一些数论难题的所谓证明,所谓公式,都是在拿误差限不明确的公式在论证,我觉得十分有失严谨.当然,如果公式的误差限找到,这些证明的过程是可以参考利用的,意义是有的,但是,现在无法肯定.
因此,我提醒数论爱好者们,包括王晓明先生,孟庆余先生,弯国强先生,多多研读经典,治学严谨一些,谦虚务实,不可累于虚名.虽然我这些话并不是什么新内容新道理,但是我强调一下,亦作为自勉吧.
而王晓明先生的索数普遍公式,实际是构造了质数连乘积的缩系(既约剩余系,简化剩余系),我于2003年受台尔曼公式和闽嗣鹤·严士健《初等数论》的启发,给出了构造缩系的更简明的方案,例如( ( 1/2+{1,2}/3+{1,2,3,4}/5+{1,2,…,6}/7 ) mod 1 ) *2*3*5*7
其中a mod 1,即是a的小数部分.
. 2004-2005年,受洪伯阳先生的《数学宝山上的明珠》的启发,在研究中国剩余定理有所改进之后,给出了另外的表示.2010年,看过了王晓明先生的文章后,发现始终没有解决误差限问题和算法复杂性问题,所以,我曾经致信王晓明先生,认为素数普遍公式,并没有完成,也不成熟.
因此,我略整理了一下网上搜集来的经典结论,打算从中获得一些启发,巩固自己的数论基础.
其中有我个人的心得,如有不足不妥,请指教.谢谢.
AAAMeissel公式及其小小改进
以下说Meissel公式之我的改写,结合了我旧日的一些思路,有空我会查一下旧日的资料,或者能发现一些或启发一些好结果.历史总会发展的.古人也是能超越的,包括过去的自己.
Y(m,n)=Phi(m,n)=card{i;i<=m, gcd(i, 2*...*p(n))=1)注: card表示集合元素个数(集合的基数或势)
即m以内与2,…,p(n)互质的数的个数,与欧拉函数相似,故采用Phi记号,希腊字母是Φ.这里p(n)则是prime(n),第n个素数.在我的数论笔记中,我称它为泛缩系计量.
Y(m,n)=Y(m,n-1)-Y([m/p(i)],n-1)注：这是个很简单的递推公式。注意,显然, Y(m,0)=m,因为所有数均与1互质.
注:这里[x]表示取整数部分,即高斯取整函数,向下取整.如[2.3]=2.也记作int(x)或floor(x).
此外还有下面的性质:
Y(a*prod(2,…,P(k))+r, k)=a*Y(prod(2,...,p(k))+Y(r,k)=a*(2-1)(3-1)...(p(k)-1)+Y(r,k)
其中prod表示连乘积,即Π(p(i)),素数p(i)的序号由1取到k.
注:我把这个式子也用于计算自变量为负数的情况,例如,定义Y(a*prod-r, k)= a*Y(prod(2,...,p(k))+Y(-r,k),计算也此一致,简化方案是利用[-x]=-ceil(x),亦作ceiling(x),例如ceil(2.3)=3, ceil(2)=2,向上取整.
记c=pi(m^(1/3)), s=pi(m^(1/2)),这里pi(x)表示x以内的素数个数,即π(x).注意,pi(c)<=cbrt(m), pi(s)<=sqrt(m).
即c=pi(cbrt(m)),cuberoot(立方根)以下的素数个数. s=pi(sqrt(m)), squareboot(平方根)以下的素数个数.易记.
则pi(m)=Y(m,c)+(s(s-1)-(c-1)(c-2))/2-sum{pi(m/p(i))}{sum表示求和,即Σ.这里范围为i=c+1到s}
注:这个公式比Meissel公式形式简洁,计算容易了一点点,应当算是略有改进吧。
Meissel公式原是这样的:设p(1),…,p(n)是最初n个素数，不大于m且不能整除任何一个p(i)的自然数个数记为Φ(m,n)那么：
Φ(m,n)=Φ(m,n-1)-Φ([m/p(i)],n-1)
给定一个自然数m,若n=π(m^(1/3))且μ=π(m^(1/2))-n,那么：
π(m)=Φ(m,n)+n(μ+1)+(μ^2-μ)/2-1-Σπ(m/p(n+k)) ,求和限:k={1,…,μ}.
例:计算m=1000时的pi(m).
易算得Y(1000, 4)=Y(1000,3)-Y(142,3)=266-38 =228
注：Y(1000,3)的计算，参见我的一个答题(题中用的是类似Legendre的算法)，见CCC相关题
s=card {2, 3, 5 ,7 ,11, 13, 17 ,19, 23 ,29, 31 } =11, c=pi (10) =4这里card表示集合元素数量(基数或势).
1/2*(s(s-1)-(c-1)(c-2)) =55-3=52
序列{ pi (m / { 11, 13, 17, 19, 23, 29, 31} ) } = { pi (90, 76, 58, 52, 43, 34, 32) }
注意:首项为25 -4,反差分(相邻项前项减后项)序列为{3, 5, 1, 1, 3, 0},即相邻两数间的素数个数
={ 24, 21, 16, 15, 14, 11, 11 }
其和为112
故pi(1000) =228 + 52 -112 =168.
AAAAAA筛法浅说
1一般筛法,先用少数几个素数筛去合数,即与它们的乘积不互素的数.然后再用更大的素数,在剩下的数里面类似筛去.如厄拉多塞筛法.
2有些筛法,在剩下的数中筛选时,根本不用到更大的素数,只是原来的素数的缩系中的同余类(我称为泛缩系)来构造出剩下来的数中的所有合数,排除它们就得到质数.这种筛法,可称为反筛法,最初使用的是辛答拉姆.其实原理很简单,就是从奇数中筛去奇合数,而奇合数由
集合{2n+1;n>=1}元素的乘积构成.
当初辛答拉姆新开一路,的确可贵.但是,辛答拉姆当初将奇合数全部 折半取整,在判别素数时又乘2加1,其实是在绕弯子,并不是必要手段,也没有任何神秘性可言,好处是可以减小存储或说明该数表的构造可以不依赖于乘积.
个人认为,不必过于在这个弯上绕来绕去,要看破这一点.
3就是下面要说到的Lehmer筛法.当然得算是一种新的筛法,思路已经又有所不同了,不应当算是厄拉多塞筛法的改进.不然,那个筛法不是源于厄拉多塞筛法这个历史源头呢?因此,我专称为Lehmer筛法.
4.我曾经考虑用素数的平方为筛子,筛得所有的无平方因子数,然后再在其中筛去合数.我发现,无平方因子数的分布规律也很复杂.但是,我觉得研究起来可能会容易一些.
BBB Lehmer筛法与Lehmer素数计数公式.
Lehmer的算法,实际是另一种筛法.我也这样想过,这样算过.想不到是闭门造车,而且是旧车和小车,竟没有造出古人造过的大车. Lehmer用他的方法算到了pi(10^10),即100亿内的素数的个数.我仅仅是此这种思路验证过pi(10000) ,pi(1000),具体情况,还得找我旧日的笔记.
于是,这里只介绍一下思路,有兴趣的朋友,可在网上搜索素数计数函数OR筛法计算公式即可找到相关资料.
Lehmer的筛法,真正是筛去合数,根据合数的因子个数来筛去.定义
P_k(m,n)=card {i; i<=m, i有k个素因子,且素因子>prime(n)}其中prime(n)也作p(n),指素数列的第n项.
注:其中这k个素因子可能相等也可不等.
显然,根据数的质因子的个数为0,1,2,3, ... ,可以将所有正整数进行分类.即m =P_0+P_1+P_2+...+P_∞,
而对于与2*3*…*p(n)互质,即只有>p(n)的素因子的数,其个数为Y(m,n)=P_0(m,n)+P_1(m,n)+P_2(m,n)+… 这里的Y(m,n)同前面讲Meissel公式时的相同,而lehmer给出了另一种算法.
注意,在一定范围内的数,素因子个数是有限的,即上式的后面从某个项开始,全部为0.例如, Lehmer就考虑m的立方根以下的最大素数p(c), m以内有三个以上比这个素数还大的素因子的数,显然是没有的.因而就不必再往上计算了.即下面所讲到的,n>=c时,P_k(m,n)=0, k>=3
下面开始计算.
P_0(m,n)=1,注:显然可以直观地看出.即没有素因子的数,当然只有{1}一个.
P_1(m,n)=pi(m)-n注:有一个大于p(n)的素因子的个数,即大于p(n)的素数的个数.
P_k(m,n). k>=3, Lehmer设法使其值为0,从而不必计算.条件是n>=c=pi(m^(1/3)).即p(n)>=p(c).注意,是>=,大于等于.一个相关细节:cbrt(m)>=p(c), p(c)是<=cbrt(m)=m^(1/3)的最大素数.
P_2(m,n)的计算.显然,当n>=s=pi(m^(1/2)),即p(n)>=sqrt(m)=m^(1/2)时, P_2(m,n)=0.注意,是>=,大于等于.因此,计算P_2(m,n)时,取n<s,只有与此对应的质数参加主要计算过程.
综上,当c<=n时,Y(m,n)=1+pi(m)-n+P_2(m,n).且P_2(m,n)的计算主要与c<=n<s对应的质数相关.即p(c)<=p(n)<p(s).一个相关细节: p(s)是<=sqrt(m)的最大素数.
Lehmer公式的重点:
P_2(m,n)=sum {pi(m/p) -pi(p)+1}{求和范围: p(n)<p<=p(s) }
何冬州注: =sum{pi(m/p)}-sum{n,n+1,…,s-1}=sum{pi(m/p)}-(n+s-1)(s-n)/2
这里的n值可在c<=n内选取.为了计算方便,还可限定在c<=n<s内选取,这一点较Meissel公式灵活,因此有些资料上也说是Meissel公式的推广.其实不仅仅是推广,而是一种新筛法思路.下面会举例,取n=5,也可计算pi(1000).
于是,pi(m)=Y(m,n)-1+n-P_2(m,n), c=<n<s.
何冬州注:即是pi(m)=Y(m,n)-sum{pi(m/p)}+n-1+(n+s-1)(s-n)/2
我的简化之一为:pi(m)=Y(m,n)-sum{pi(m/p)}+(s(s-1)-(n-1)(n-2))/2
仅仅是使其易记易用了一点点.但对于我个人而言,很有好处.当取n=c时,与Meissel公式一致.
{
其中Y(m,n)的计算过程,可以用前面讲Meissel公式时用到的,这里重录一下:
Y(m,n)=Y(m,n-1)-Y([m/p(i)],n-1)注：这是个很简单的递推公式。注意,显然, Y(m,0)=m,因为所有数均与1互质.
注:这里[x]表示取整数部分,即高斯取整函数,向下取整.如[2.3]=2.也记作int(x)或floor(x).
此外还有下面的性质:
Y(a*prod(2,…,P(k))+r, k)=a*Y(prod(2,...,p(k))+Y(r,k)=a*(2-1)(3-1)...(p(k)-1)+Y(r,k)
}
Lehmer公式应用举例:
用来计算pi(m),m=1000, c=4, s=pi {2,3,5,7,11,13,17,19,23,29,31}=11
计算:取n=5, Y(1000,5)=Y(1000,4)-Y(1000\11,4)=228-21=207,这里用a\b表示a/b的整数部分.
注:其中利用到了前面算过的结果Y(1000,4)=228.另外,Y(90,4)=Y(90,3)-Y(12,3)= card {13到90以内形如30k+{1,7,11,13,17,19,23,29}的数} =21.(=5+16或24-3)
sum{ pi(m\{13,…,31})}=112-pi(1000\11)=112-pi(90)=112-24=88.注:这里利用了前面的计算结果sum{ pi(m\{11,…,31})}=112.
11*10/2-4*3/2=55-6=49
于是pi(1000)=207+49-88=168
我们可以看到,Lehmer公式可以充分转化与利用已有成果,我想lehmer必有一套流程,可以在特定的一组数内批量利用,计算pi(x)值.
我曾经在不知Meissel公式与Lehmer公式时独立计算pi(x),也曾有此想法,作了大量笔记.
CCCAAA：Lengdre素数计数公式,容斥原理=包含排除原理=逐步淘汰原则
参考:欧拉函数,既约剩余系=简化剩余系=缩系,缩系的构造, Mobius函数
基础：记号同前：
Y(m,n)=Phi(m,n)=card{i;i<=m, gcd(i, 2*...*p(n))=1)注: card表示集合元素个数(基数或势)
即m以内与2,...,p(n)互质的数的个数,与欧拉函数相似,故采用Phi记号,希腊字母是Φ.
记s=pi(m^(1/2)),这里pi(x)表示x以内的素数个数,即π(x).注意, pi(s)<=sqrt(m);而s=pi(sqrt(m)),即squareboot(平方根)以下的素数个数.易记.
易见Y(m, s) = pi (m) -pi (s) +1,即得
Lengdre素数计数公式:pi(m) = -1 + pi(s) + Y(m, s)
以m=100为例说明,为方便,用a \ b表示a/b的整数部分.此时pi(s)=pi(sqrt(100))=pi(10)=4
Y(m,s)=card{i;i<=100, gcd(i, 2*...*7)=1)= 100 -1- card {100内能被2, 3, 5, 7之一整除的数}
=100 - 100 \ { 2, 3, 5, 7 }+ (100 \2) \ {3, 5, 7} + (100\3) \ {5,7} + (100 \5) \ 7 -(100 \2\3 ) \ {5,7}-(100\2\5) \7
=(100- 50-33-20-14+16+10+7+6+4+2-3-2-1)=22
故pi(100)=-1+4+22=25
注:可以看到,有些项是可以继承利用的;列成表格,类似于卡诺图,元素个数构成2的方幂.
注:试利用Y(m,n)=Y(m,n-1)-Y([m/p(i)],n-1)简化计算:
100-14-(100 \{2,3,5}-14\{})+(100\{2*3,2*5,3*5}-14\{})-(100\(2*3*5)-14\())=(100-14-(50+33+20-7-4-2)+(16+10+6-2-1)-(3))=22
注:试利用Meissel公式来计算,看看改进了什么.快在什么地方.
pi(m)=Y(m,c)+(s(s-s)-(c-1)(c-2))/2-sum{pi(m/p(i))}{sum表示求和,即Σ.这里范围为i=c+1到s}
m=100, c=card {2,3}=2, s=4,pi(100)=Y(100,2)+ (4*3-1*0)/2-sum{pi {100/5, 100/7}}
=(100-50-33+16)+6-sum(card{2,3,5,7,11,13,17,19}, card{2,3,5,7,11,13})=17+22-8-6=25.简单多了.
CCC相关题:
1到1000中所有不能被2、3、5整除的自然数有多少个？算式怎么列？
http://zhidao.baidu.com/question/435220655.htm
其中的容斥原理,就是Legendre算法的原理.
解：以下用[]表示取整数部分,即高斯取整函数.
计算过程是将下面{}内的各行的计算项取代数和.
{
1000,
-[1000/2]-[1000/3]-[1000/5] = -500 -333-200 =-1033
+[[1000/2]/3] +[[1000/2]/5] +[[1000/3]/5] =[500/3]+[500/5]+[333/5]=166+100+66=332
-[ [[1000/2]/3]/5 ]=-[166/5] =-33
}
=1000-(500+333+200) +(166+100+66)-33
=-33+332-33=266
原理:容斥原理(又称作包含排除原理或逐步淘汰原则,可参考百度百科-容斥原理)
推广:
1到X中所有不能被2, 3, 5, ... , p(i), ..., p(n)整除的自然数的个数
=sum{
+X,
-{ [X/2]+[X/3]+...+...+[X/p(n)] }
+{
+[X/2/3]+[X/2/5+....+[X/2/p(n)]
+[x/3/5]+... +[x/2/p(n)]
+... +...
++[X/p(n-1)/p(n)]
}
-...
+...
+ (-1)^n * [X/2/3/.../p(n)]
}
注#1:这里的[]表示取整数部分,即高斯取整函数.
注#2:计算时可以使用[X/(2*3)]=[ [X/2] /3 ]= [ [X/3] /2 ]
注#3:在数论中,欧拉函数有类似的形式与性质
注#4:代数和的正负号=(-1)^数的奇次方质因子的个数(或者说,去除平方因数之后的剩下质因子的个数为奇则取负,为偶数包括0则取正).这在数论中称作mobius函数(莫比乌斯),参考百度百科-数论函数-积性函数.
优质内容筛选与推荐>>1、04_Javascript初步第二天（下）
2、回头再说 002
3、selenium webdriver 学习笔记(一)
4、缓存
5、Linux命令行与图形界面切换方法