基本介紹
- 中文名：素數公式
- 外文名：Prime formula
- 別稱：質數公式
- 定義：表示一種能夠僅產生質數的公式
- 特點：產生的結果都是質數
定理簡介,初等證明,素數簡介,通項公式,密度公式,
定理簡介
素數定理描述素數的大致分布情況。
素數的出現規律一直困惑著數學家。一個個地看，素數在正整數中的出現沒有什麼規律。可是總體地看，素數的個數竟然有規可循。對正實數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－艾狄胥的證明正好表示，看似初等的組合數學，威力也可以很大。 但是，有必要指出的是，雖然該初等證明只用到初等的辦法，其難度甚至要比用到複分析的證明遠為困難。
素數簡介
概念
通項公式
n的點集分兩組，一組為偽素數的變數集，一組為素數的變數集合，其中偽素數的變數集合有以下方程式來確定：
素數變數n(x,y)的充分必要條件為：
- n(x,y)為偶數時：
2.n(x,y)為奇數時：
滿足以上方程則為素數的變數,但方程不包括2,3這兩個素數。
偽素數變數n(x,y)的充分必要條件為：
- n(x,y)為偶數時：
2.n(x,y)為奇數時：
密度公式
根據 ：
構造一函式如下：
其中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整除，所以該合數分解得到的素因數肯定不在假設的素數集合中。
●因此無論該數是素數還是合數，都意味著在假設的有限個素數之外還存在著其他素數。
●對任何有限個素數的集合來說，用上述的方法永遠可以得到有一個素數不在假設的素數集合中的結論。
●所以原先的假設不成立。也就是說，素數有無窮多個。
對於一定範圍內的素數數目的計算
儘管整個素數是無窮的，仍然有人會問“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
Next
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
Next
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
End If
Next
If I >= N Then
Call MR
End If
Next
End Sub
Sub MR()
Columns("A:A").Select
Selection.Sort Key1:=Range("A1"), Order1:=xlAscending, Header:=xlGuess, _
OrderCustom:=1, MatchCase:=False, Orientation:=xlTopToBottom, SortMethod _
:=xlPinYin, DataOption1:=xlSortNormal
Columns("B:B").Select
Selection.Sort Key1:=Range("B1"), Order1:=xlAscending, Header:=xlGuess, _
OrderCustom:=1, MatchCase:=False, Orientation:=xlTopToBottom, SortMethod _
:=xlPinYin, DataOption1:=xlSortNormal
Columns("C:C").Select
Selection.Sort Key1:=Range("C1"), Order1:=xlAscending, Header:=xlGuess, _
OrderCustom:=1, MatchCase:=False, Orientation:=xlTopToBottom, SortMethod _
:=xlPinYin, DataOption1:=xlSortNormal
Columns("D:D").Select
Selection.Sort Key1:=Range("D1"), Order1:=xlAscending, Header:=xlGuess, _
OrderCustom:=1, MatchCase:=False, Orientation:=xlTopToBottom, SortMethod _
:=xlPinYin, DataOption1:=xlSortNormal
Columns("E:E").Select
Selection.Sort Key1:=Range("E1"), Order1:=xlAscending, Header:=xlGuess, _
OrderCustom:=1, MatchCase:=False, Orientation:=xlTopToBottom, SortMethod _
:=xlPinYin, DataOption1:=xlSortNormal
Columns("F:F").Select
Selection.Sort Key1:=Range("F1"), Order1:=xlAscending, Header:=xlGuess, _
OrderCustom:=1, MatchCase:=False, Orientation:=xlTopToBottom, SortMethod _
:=xlPinYin, DataOption1:=xlSortNormal
Range("Q1").FormulaR1C1 = "=COUNTIF(C[-16]:C[-11],"">0"")"
Range("R1").FormulaR1C1 = "=COUNTIF(C[-17],"">0"")"
Range("S1").FormulaR1C1 = "=COUNTIF(C[-17],"">0"")"
Range("T1").FormulaR1C1 = "=COUNTIF(C[-17],"">0"")"
Range("U1").FormulaR1C1 = "=COUNTIF(C[-17],"">0"")"
Range("V1").FormulaR1C1 = "=COUNTIF(C[-17],"">0"")"
Range("W1").FormulaR1C1 = "=COUNTIF(C[-17],"">0"")"
End Sub
Function WS(A As Variant, B As Variant) As Variant
If A Mod 2 = 1 And B Mod 2 = 1 Then
WS = 3 * A * B + 2 * (A + B) + 1
End If
If A Mod 2 = 0 And B Mod 2 = 0 Then
WS = 3 * A * B + (A + B)
End If
If A Mod 2 = 1 And B Mod 2 = 0 Then
WS = 3 * A * B + A + 2 * B
End If
If A Mod 2 = 0 And B Mod 2 = 1 Then
WS = 3 * A * B + B + 2 * A
End If
WS = WS
If A < B Then
WS = 0
Else
WS = WS
End If
WS = WS
End Function
Function WSF(A As Variant, B As Variant, N As Long) As Variant
Dim d As Variant
d = WS(A, B) - 3 + 2 * (Sin(3.14159265358979 * WS(A, B) / 2)) ^ 2
If WS(A, B) <= WS(N, N) And d Mod 5 <> 0 Then
WSF = WS(A, B)
Else
WSF = 0
End If
End Function
素數逼近函式
