素数公式

本词条缺少名片图，补充相关内容使词条更完整，还能快速升级，赶紧来吧！

质数公式，又称素数公式，在数学领域中，表示一种能够仅产生质数（素数）的公式。即是说，这个公式能够一个不漏地产生所有的质数，并且对每个输入的值，此公式产生的结果都是质数。由于质数的个数是不可数的，因此一般假设输入的值是自然数集（或整数集及其它可数集）。迄今为止，利用程序人们已经找到易于计算且符合上述条件的质数公式，但对于质数公式应该具备的性质已经有了大量的了解。

中文名

素数公式

外文名

Prime formula

别称

质数公式

定义

表示一种能够仅产生质数的公式

特点

产生的结果都是质数

1 简介

简介

素数定理描述素数的大致分布情况。

素数的出现规律一直困惑著数学家。一个个地看，素数在正整数中的出现没有什么规律。可是总体地看，素数的个数竟然有规可循。对正实数x，定义π(x)为不大于x的素数个数。数学家找到了一些函数来估计π(x)的增长。以下是第一个这样的估计。 π(x)≈x/ln x 其中ln x为x的自然对数。上式的意思是当x趋近∞，π(x) 和x/ln x的比趋近1（注：该结果为高斯所发现）。但这不表示它们的数值随着x增大而接近。下面是对π(x)更好的估计： π(x)=Li (x) + O (x e^(-(ln x)^(1/2)/15)，当 x 趋近∞。其中 Li(x) = ∫(dt/ln x2,x)，而关系式右边第二项是误差估计，详见大O符号。下表比较了π(x)，x/ln x和Li(x)： x π(x) π(x) - x/ln(x) Li(x) - π(x) x/π(x)

素数定理可以给出第n个素数p(n)的渐近估计： :p(n)～n/ln n. 它也给出从整数中抽到素数的概率。从不大于n的自然数随机选一个，它是素数的概率大约是1/ln n。这定理的式子於1798年法国数学家勒让德提出。1896年法国数学家哈达玛(JacquesHadamard)和比利时数学家普森(Charles Jean de la Vallée-Poussin)先後独立给出证明。证明用到了复分析，尤其是黎曼ζ函数。因为黎曼ζ函数与π(x)关系密切，关于黎曼ζ函数的黎曼猜想对数论很重要。一旦猜想获证，便能大大改进素数定理误差的估计。1901年瑞典数学家Helge von Koch证明出，假设黎曼猜想成立，以上关系式误差项的估计可改进为 :π(x)=Li (x) + O (x^(1/2) ln x) 至於大O项的常数则还未知道。

初等证明

素数定理有些初等证明只需用数论的方法。第一个初等证明於1949年由匈牙利数学家保罗·艾狄胥（“爱尔多斯”，或“爱尔多希”）和挪威数学家阿特利·西尔伯格合作得出。在此之前一些数学家不相信能找出不需借助艰深数学的初等证明。像英国数学家哈代便说过素数定理必须以复分析证明，显出定理结果的「深度」。他认为只用到实数不足以解决某些问题，必须引进复数来解决。这是凭感觉说出来的，觉得一些方法比别的更高等也更厉害，而素数定理的初等证明动摇了这论调。Selberg－艾狄胥的证明正好表示，看似初等的组合数学，威力也可以很大。但是，有必要指出的是，虽然该初等证明只用到初等的办法，其难度甚至要比用到复分析的证明远为困难。

素数简介

概念

质数又称素数。指在一个大于1的自然数中，除了1和此整数自身外，不能被其他自然数整除的数。质数是与合数相对立的两个概念，二者构成了数论当中最基础的定义之一。基于质数定义的基础之上而建立的问题有很多世界级的难题，如哥德巴赫猜想等。截至2012年6月底，质数尚未完全找到通项公式。

素数及伪素数通项公式

n的点集分两组，一组为伪素数的变量集，一组为素数的变量集合，其中伪素数的变量集合有以下方程式来确定：

素数变量n(x,y)的充分必要条件为：

n(x,y)为偶数时：

2.n(x,y)为奇数时：

满足以上方程则为素数的变量,但方程不包括2,3这两个素数。

伪素数变量n(x,y)的充分必要条件为：

n(x,y)为偶数时：

2.n(x,y)为奇数时：

素数密度公式

根据：

构造一函数如下：

1-1

其中a为常数且

根据1-1性质以多项式

为

中的指数

，结合公式1-1

得素数密度公式：

此公式中定义1为素数

质数的无穷性的证明

质数的个数是无穷的。最经典的证明由欧几里得证得，在他的《几何原本》中就有记载。它使用了现在证明常用的方法：反证法。具体的证明如下：

●假设质数只有有限的n个，从小到大依次排列为p1，p2，……，pn，设 N = p1 × p2 × …… × pn，那么，N+1是素数或者不是素数。

●如果N+1为素数，则N+1要大于p1，p2，……，pn，所以它不在那些假设的素数集合中。

●如果N+1为合数，因为任何一个合数都可以分解为几个素数的积；而N和N+1的最大公约数是1，所以N+1不可能被p1，p2，……，pn整除，所以该合数分解得到的素因数肯定不在假设的素数集合中。

●因此无论该数是素数还是合数，都意味着在假设的有限个素数之外还存在着其他素数。

●对任何有限个素数的集合来说，用上述的方法永远可以得到有一个素数不在假设的素数集合中的结论。

●所以原先的假设不成立。也就是说，素数有无穷多个。

其他数学家也给出了他们自己的证明。欧拉利用黎曼ζ函数证明了全部素数的倒数之和是发散的，恩斯特·库默的证明更为简洁，Hillel Furstenberg则用拓扑学加以了证明。

对于一定范围内的素数数目的计算

尽管整个素数是无穷的，仍然有人会问“100000以下有多少个素数?”，“一个随机的100位数多大可能是素数?”。素数定理可以回答此问题。

素数输出及个数计算

利用excel宏能够精确计算每个周期内的素数总数，不过不含2,3的数量。以下程序在excel 2003能够计算361个周期以内的素数。运行前必须在单元格O1输入不大于361的自然数，周期数361，运行需要约16分钟，小周期内运行很快，程序中ws(a,b)就是伪素数的变量函数，N为周期，程序运行结束后单元格Q1为全部统计素数总数，R1~W1为各列素数数量，如果想计算周期大于361时，必须修改以下程序，本程序已经优化，比任何筛选程序运行都要快，以下是本程序代码：

Sub 求素数()

Dim N As Long, R As Long, J As Long, I As Long, k As Long, Y As Long, y1 As Long

Dim S1 As String, S As String

N = Range("O1") '程序运行前请在表格O1输入不大于361的周期数

For Y = 1 To WS(N, N) Step 1

If WS(Y, 2) <= WS(N, N) Then

R = Y

End If

Range("A1:N65536") = ""

Range("P1:X1") = ""

Range("P1") = "变量为" & WS(N, N) & "以内素数合计"

Range("A1") = 5

For k = 1 To WS(N, N) Step 1

y1 = (k - 3 + 2 * (Sin(3.14159265358979 * k / 2)) ^ 2)

If y1 Mod 5 = 0 Then

k = k + 1

Else

k = k

End If

If k <= 65536 Then

S1 = "A" & k

ElseIf k > 65536 And k <= 65536 * 2 Then

S1 = "B" & k - 65536

ElseIf k > 65536 * 2 And k <= 65536 * 3 Then

S1 = "C" & k - 65536 * 2

ElseIf k > 65536 * 3 And k <= 65536 * 4 Then

S1 = "D" & k - 65536 * 3

ElseIf k > 65536 * 4 And k <= 65536 * 5 Then

S1 = "E" & k - 65536 * 4

ElseIf k > 65536 * 5 And k <= 65536 * 6 Then

S1 = "F" & k - 65536 * 5

End If

Range(S1) = 3 * k + 1 + (Sin(3.14159265358979 * k / 2)) ^ 2

For I = 1 To N Step 1

For J = 1 To R Step 1

If WSF(J, I, N) > 0 And WSF(J, I, N) <= WS(N, N) Then

If WSF(J, I, N) <= 65536 Then

S = "A" & WSF(J, I, N)

ElseIf WSF(J, I, N) > 65536 And WSF(J, I, N) <= 65536 * 2 Then

S = "B" & WSF(J, I, N) - 65536

ElseIf WSF(J, I, N) > 65536 * 2 And WSF(J, I, N) <= 65536 * 3 Then

S = "C" & WSF(J, I, R) - 65536 * 2

ElseIf WSF(J, I, N) > 65536 * 3 And WSF(J, I, N) <= 65536 * 4 Then

S = "D" & WSF(J, I, N) - 65536 * 3

ElseIf WSF(J, I, N) > 65536 * 4 And WSF(J, I, N) <= 65536 * 5 Then

S = "E" & WSF(J, I, N) - 65536 * 4

ElseIf WSF(J, I, N) > 65536 * 5 And WSF(J, I, N) <= 65536 * 6 Then

S = "F" & WSF(J, I, N) - 65536 * 5

End If

If WSF(J, I, N) > 0 Then

S = S

Range(S) = ""

Else

S = ""

End If

If I >= N Then

Call MR

End If

End Sub

Sub MR()

Columns("A:A").Select

Selection.Sort Key1:=Range("A1"), Order1:=xlAscending, Header:=xlGuess, _

OrderCustom:=1, MatchCase:=False, Orientation:=xlTopToBottom, SortMethod _