|
关于素数个数的一些经典公式介绍
Willans素数公式
(1)
对每个整数j≥1,令
F(j)=[(cos^2)π((j-1)!+1/j)]
这里[x]表示x的取整部分.于是对每个整数j>1,当j为素数时F(j)=1,否则F(j)=0,并且F(1)=1.因此
π(n)=-1+ΣF(j) (j=1至n)
(2)
H(j)=(sin^2)π(((j-1)!)^2/j)/(sin^2)π/j
π(n)=ΣH(j) (j=2至n)
Minac素数公式
π(n)=Σ[(j-1)!+1/j-[(j-1)!/j]]
证:
若n≠4不是素数,则n除尽(n-1)!.这是因为n或者写成n=ab,其中2≤a,d≤n-1并且a≠b,或者n=p^2≠4.对于前者,n除尽(n-1)!;对于后者,2<p≤n-1=(p^2)-1,
从而2p≤(p^2)-1.于是n除尽2p^2=p*2p,从而n除尽(n-1)!
根据Wilson定理,对每个素数j,(j-1)!+1=kj,其中k为整数,于是
[(((j-1)!+1)/j)-[(j-1)!/j]]=[k-[k-(1/j)]]=1
若j不是素数并且j≥6,则(j-1)!=kj,其中k为素数.由上面注记可知
[((j-1)!+1)/j-[(j-1)!/j]]=[k+1/j-(k)]=0
最后对j=4,则
[(3!+1)/4-[3!/4]]=0
证毕.
勒让德素数公式
1808年勒让德经过认真研究用爱氏筛法给出了
π(n)=π(n^0.5)-1+Σμ(d)[n/d]
其中d过所有正整数,并且d的素因子均不超过n^0.5
μ(d)定义是:μ(1)=1,μ(n)=(-1)^r,若n是r个不同素数的乘积,μ(n)=0,若某个素数的平方除尽n.
施承忠 2009.6.27
|
|