這部份的參考資料還多了一份 pdf
16. 質數個數問題
這符號是 π(x)，但為顯示不正常，一律用 pi(x) 表示。
pi(x) 為一函式，代表的是小於等於 x 以下的所有質數個數為幾個，
如 100 以下之質數有 25個， pi(100) = 25。然而讓人感興趣的是，
有沒有一個公式可以推估小於 x 值時，約有幾個質數。
這是一個公式，用來估計小於 x 之質數約有幾個。公式為
pi(x) ~ x / log(x)
別忘了，這裡的 log(x) 代表的是 loge(x)。
若是在 x 不大的情況之下，實際上直接用篩法去算便可，這部份只是做簡單的估計值，
且估計出來的個數，將比實際的個數還要少。wiki 另也有一些不等式
pi(x) < 1.25506 * x / logx , for x > 1
x / ( log2 + 2) < pi(x) < x / (logx - 4) , for x >=55
而之前看到一些文章更可以把範圍再縮小些，原作應是 Pierre Dusart
( x / logx ) * ( 1 + 0.922 / logx ) < pi(x) < ( x / logx) * ( 1 + 1.2762 / logx), for x>598
這有什麼好處？簡單的說，上限值可當作是質數表大小的參考。
17. 第 n 個質數
p(x)~xlogx
p(x)~x(logx + log log x - 1)
這部份有其它相關之公式，詳見本文開頭之 pdf 連結。
18. Euler's totient function
φ (n)，歐拉函式，用來計算小於 n 之正整數中，正 n 互質整數之個數。如 與 8 互質的有 1,3,5,7，共四個數，故 φ (8) = 4
以 φ (72) 為例，大致上計算如下
φ (72) = φ (23 * 32) = 23-1 * (2-1) * 32-1 * ( 3-1 ) = 24，故有小於 72 之正整數，且於72互質之正整數有24個。
19. 費馬數 (Fermat Number)
定義為 Fn = 22^n+1，
F0 = 2+1= 3
F1 = 4+1= 5
F2 = 16+1 = 17
F3 = 256 + 1 = 257
這些都屬費馬數。一開始費馬猜想，所有費馬數均為質數，最後被 Euler 推翻。於是才有費馬檢驗測試
設 Fn = 22^n+1 為第 n 個費馬數，Fn is a prime iff 3(Fn-1)/2 mod Fn = -1
基本性質有四個，都是遞回關係，這裡只列出二個：
(a) Fn = (Fn-1 - 1)2 + 1
(b) Fn = Fn-12 - 2(Fn-2-1)2
20. 梅森數(Mersenne )
梅森數定義為 Mn = 2n-1，
而梅森數也未必為梅森質數，於是才有 盧卡斯-萊默檢驗法 (Lucas–Lehmer primality test)，敘述大致如下
令 Mn = 2n-1，(其中 n 為質數，否則 Mn 就是合數)，並定義序列 Si
if(i ==0) Si=4;
else if(i >0) Si= (Si-1)2 - 2，
Mn is a prime , iff Sn-2 mod Mn = 0
重點是，在 i > 0 的時候，要迭代到什麼時候才可停下來？答案是：p-2 次。
參考資料
wiki - Mersenne prime
wiki - Fermat number
wiki - Carmichael number
wiki - Modular exponentialiation
wiki - Montgomery reduction
wiki - Fermat primality test
wiki - Miller-Rabin primality test
wiki - Lucas Lehmer test for Mersenne numbers
wiki - AKS primality test
wiki - Prime-counting function
wiki - Euler's totient function
留言列表
開發手札 (2)
{{ article.title }}