這部份的參考資料還多了一份 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 - Sieve of Eratosthenes

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

edisonx 發表在 痞客邦 PIXNET 留言(0) 人氣()