质数定理是在公元前250年由古希腊数学家埃拉托塞尼提出的筛选素数的方法，即要得到不大于某个自然数N的所有素数，只要在2---N中将不大于√N的素数的倍数全部划去即可，后来又有发展。

质数定理

素数定理介绍

素数定理的深入开发(（1）素数定理的幂型式 （2）起始数内素数分布)

（1）、自然质数定理

设Pi（N）表示不大于N的质数的总个数，那么，有如下公式成立：

Pi（N）≡INT { N×（1－1/P1）×（1－1/P2）×…×（1－1/Pm）+m －1 }

Pi（N）≈Psha（N）≡Li（N）×（1 －（1+1 /（Ln（N）－4））/√N ）

式中INT { } 表示对{ } 内公式展开式的每一项取整后再进行加减运算，P1、P2、…、Pm 为所有不大于√N 的m 个质数，Li（N）为高斯的自然对数倒数的积分公式，Ln（N）为自然对数。

（2）、孪生质数定理

设Tp（N）表示不大于N的孪生质数的数量，那么，有如下公式成立：

Tp（N）≈Tsha（N）≡2 / N ×Ctwin ×（Psha（N））^2

式中Ctwin为孪生质数常数。

（3）、偶数质数定理

设Gp（N）表示偶数N表为两个奇质数Gp与N－Gp之和的表法的数量，那么，有如下公式成立：

Gp（N）≈Gsha（N）≡Ctwin ×K×4 / N ×Psha（N/2）×（Psha（N）－Psha（N/2））

K =∏（（Pc －1 ）/（Pc －2 ））≥1

式中Ctwin为孪生质数常数，Pc为不大于√N且能整除偶数N的奇质数。

（4）、奇数质数定理

设Rp（N）表示奇数N 表为三个奇质数之和的表法的数量，那么，有如下公式成立：

Rsha（N）≡Ctwin / Cs（N）×4/3×Psha（N/2）×（Psha（N）－Psha（N/2））/ Ln（N）

Cs（N）=∏（1+1 /（（Ps －1）×（Ps －2）））≤Csha

式中Ctwin为孪生质数常数，Ps为不大于√N且能整除奇数N的奇质数，Ln（N）为自然对数。

素数普遍公式

公元前250年同样是古希腊的数学家埃拉托塞尼提出一种筛法：

（一）

“要得到不大于某个自然数N的所有素数，只要在2---N中将不大于√N的素数的倍数全部划去即可”。

（二）

将上面的内容等价转换：“如果N是合数，则它有一个因子d满足1<d≤√N”。（《基础数论》13页，U杜德利著，上海科技出版社）。.

（三）

再将（二）的内容等价转换：“若自然数N不能被不大于(根号)√N的任何素数整除，则N是一个素数”。见（代数学辞典[上海教育出版社]1985年。屉部贞世朗编。259页）。

（四）

这句话的汉字可以等价转换成为用英文字母表达的公式：

N=p1m1+a1=p2m2+a2=......=pkmk+ak 。(1)

其中 p1，p2，.....，pk表示顺序素数2，3，5，,,,,。a≠0。即N不能是2m+0，3m+0，5m+0，...，pkm+0形。若N<P（k+1）的平方 [注：后面的1，2，3，....，k，（k+1）是脚标，由于打印不出来，凡字母后面的数字或者i与k都是脚标] ，则N是一个素数。

（五）

可以把（1）等价转换成为用同余式组表示：

N≡a1(modp1)， N≡a2(modp2)，.....，N≡ak(modpk)。 (2)

例如，29，29不能够被根号29以下的任何素数2，3，5整除，29=2x14+1=3x9+2=5x5+4。 29≡1(mod2)，29≡2(mod3)， 29≡4(mod5)。29小于7的平方49，所以29是一个素数。

以后平方用“*”表示，即：㎡=m*。

由于（2）的模p1，p2，....，pk 两两互素，根据孙子定理(中国剩余定理）知，（2）在p1p2.....pk范围内有唯一解。

例如k=1时，N=2m+1，解得N=3，5，7。求得了（3，3*）区间的全部素数。

k=2时，N=2m+1=3m+1，解得N=7，13，19； N=2m+1=3m+2，解得N=5，11，17，23。求得了（5，5*）区间的全部素数。

k=3时,

---------------------| 5m+1-|- 5m+2-| 5m+3,| 5m+4.|

---------------------|---------|----------|--------|---------|

n=2m+1=3m+1= |--31----|--7, 37-|-13,43|--19----|

n=2m+1=3m+2= |-11,41-|-17,47-|--23---|---29---|

------------------------------------------------------------

求得了（7，7*）区间的全部素数。仿此下去可以求得任意大的数以内的全部素数。

质数定理

高斯发现了：

∏（X）=X/㏑X.

这个关系叫做质数定理，是高斯1791年发现的，但直到1896年才得到证明。

高斯（1777～1855年，关于高斯与质数定理，请参阅凡异出版社，伟大数学家的一生——高斯）

14岁那年收到一本对数的书；次年，研究书上所附的质数表，发现了这个定理。终其一生，高斯一直很注意质数分布，并且花了很多功夫去计算。高斯写信给他学生安克（Encke）说他「时常花费零星的片刻计算1000个连续整数（如18001到19000）中有多少质数」，最后他竟能列出三百万以下的所有质数，并且拿来和他的推测公式比较。

质数定理说π(x)是渐近地，即相对误差趋近于0，等于x/logx。但是如果拿x/logx与π(x)的图形加以比较，则可看出，虽然x/logx反映了π(x)行为的本质，却还不足以说明π(x)的平滑性。

寻找质数的筛法与质数的公式是有关系的：

埃拉托塞尼筛法与公式的关系

素数定理介绍

在数论中，有一所谓的素数定理，顾名思义，凡有关素数的分布之事宜，均须以此定理为准则，来计算分布的情况。譬如，所谓的研究哥德巴赫猜想之工具的等价数列i+kn中素数之分布的函数π(x;k,i)，就是以素数定理中的Lix(x)函数为基准，被欧拉函数ψ(k)所除而成立：

π(x;k,l)={Lix/ψ(x)}+o{xe^(-c(logx^1/2))

其中，o(x)函数为等价函数，用以修正Lix(x)函数在计算上的误差。

素数定理的深入开发

素数定理：揭示了素数在自然数中的平均分布情况。

π(x)≈x/Lnx表示

“ 给定数以内素数的个数约等于给定数与该数自然对数的比值。”

用π(x)表示不超过x的素数个数,

当x足够大时,π(x)≈x/(Lnx-1.08366)

（1）素数定理的幂型式

将素数定理用幂与指数方式来表示:

给定数以内素数的个数约等于幂与该幂指数的比值。

有,π(e^m)≈(e^m)/m 和 π(e^2m)≈(e^2m)/2m,

因为, e^m·e^m==e^(m+m)==e^2m,

所以,

``````````e^(2m)``e^m·e^m```e^m```1

π(e^2m)≈------==---------==----·-·e^m

...........2m......m·2......m.....2

换用数与对数来表示:

π(x·x)≈（(x/Lnx)/2）·x

素数定理的新表达式为:

“ 给定数以内素数的个数约等于

该数的开方数内素数的个数的一半与该数开方数的积。”

例如:

10的幂,,,,,,,实际解,,,,,,,,,,,,,,新公式解

x````````````π(x)```````````((x/Lnx)/2)·x

10^4..........1229...........24/2·10^2==12·10^2

10^6.........78498..........145/2·10^3==73·10^3

10^8.......5761455.........1086/2·10^4==543·10^4

10^10....455052511.........8687/2·10^5==4344·10^5

10^12..37607912018........72382/2·10^6==36191·10^6

10^14...3204941750802....620421/2·10^6==310210·10^7

（2）起始数内素数分布

(x·x)以内素数个数y的公式:

y(x)==(x·x+12x-13)/8.........x为>1的奇数

设M=(x·x),则M数以内素数个数π(M)的公式及简化式,如下:

π(M)==(M+12(√M)-13)/8

π(M)==(M+12(√M-1))/8

即“M数以内素数个数,等于该数八分之一,加上该数开方数的1.5倍。”

与奇数(2n+1)的顺序数n相关的(2n+1)的平方数内素数的个数的公式:

M==(2n+1)(2n+1)===(2n+1)^2==n^2+4n+1==奇数的平方数

π(M)==π((2n+1)^2)==[(n+7)/2]·n=对应参数·奇数的顺序数

即“奇数的平方数内素数的个数,等于该奇数的顺序数与对应参数的积”（3）素数定理扩展到平面（二次数）形式：开方数做单位　求某素数的平方数以内的素数的个数的方法，例如：31·31,

把961分成31行,31列,各列顺序为{1,2,3,4,5,6,...,30,31}

按次序去掉所有含开方数内素数做素因子的合数，剩下的就是素数。

先去掉含(961-1)中的素因子的合数.

开方数做单位，就是筛除的数，单位是列，“1”列=1开方数=1竖条。

去掉素因子为2的合数，即去掉(第1列+1)的一半,去掉偶顺序数的列。

去掉素因子为3的合数，即第1列去掉1/6的数,再去掉1/6的列。

去掉素因子为5的合数，即第1列去掉1/15的数,再去掉1/15的列。

去掉{2,4,6,8,10,12,...24,26,28,30}{3,9,15,21,27}{5，25}

此时，第一列只留下{7,11,13,17,19,23,19,31},

留下的完整列的顺序为{7,11,13,17,19,23,19,31},

留下的列的顺序数为去掉了素因子素数的其他素数,

再去掉含(961-1)中的非素因子(符号“P”)的合数.

利用各级筛法的互素数表求，等于[P,(961/P)]区间的互素数个数。

含素因子7的奇合数为

7·{7.11,13,17,19,23,29,31;37,41,43,47,49,53,..133,137}

奇合数的个数,每30有8个数,区间为[7,137.2],有(36/31)列个数。

其他素数P的奇合数,利用在[P,(961/P)]区间的互素数表等于素数表求:

11至87.4之间有19个素数,含素因子11的奇合数的列数==19/31,

13至73.93之间有16个素数,含素因子13的奇合数的列数==16/31,

17至56.6之间有10个素数,含素因子17的奇合数的列数==10/31,

19至50.5之间有8个素数,含素因子19的奇合数的列数==8/31,

23至41.8之间有23·{23,29,31,37,41},,含23的奇合数的列数=5/31。

29至33.2之间有29·{29,31},含素因子29的奇合数的列数=2/31。

31仅自己1个。31·,含素因子31的奇合数的列数=1/31。

7,11,13,17,19,23,29,31列中,要去掉的列为:

(36+19+16+10+8+5+2+1)/31==97/31==3+(4/31)==3列多领头4个.

将其放在{7,11,13}列内,留下的列为{17,19,23,29,31},欠领头4个。

留下的5列为“开方数内奇素数个数10的一半”。31·5-4==151个

还留下的列是第一列中的素数，11个。总计素数:151+11=162个.

与实际素数个数一样