Prime

使用加法,徹底分解數字

例如5 = 1 + 1 + 1 + 1 + 1。

不可分解的單元是1。不稀奇。

使用乘法,徹底分解數字

加法換成乘法之後,事情變化多端,例如5 = 5,例如6 = 2 × 3。可以發現,2、3、5、7、11等,是不可分解的單元。至於4、6、8、9、10等,可以再分解。

不可分解的單元叫做「質數」!非常稀奇!

接下來要介紹的演算法有:從小到大列出質數(建立質數表)、判斷一個數是不是質數(質數測試)、使用乘法湊得給定的數(質因數分解)。

Prime Generation

Prime Generation

製作質數表。

  2   3   5   7  11  13  17  19  23  29
 31  37  41  43  47  53  59  61  67  71
 73  79  83  89  97 101 103 107 109 113
127 131 137 139 149 151 157 163 167 173
179 181 191 193 197 199 211 223 227 229
233 239 241 251 257 263 269 271 277 281
......

Prime Generation: Sieve of Eratosthenes

Sieve of Eratosthenes

這是一個製作質數表的演算法。簡稱「篩法」。

列出所有正整數。從2開始,刪掉2的倍數。找下一個未被刪掉的數字,找到3,刪掉3的倍數。找下一個未被刪掉的數字,找到5,刪掉5的倍數。如此不斷下去,就能刪掉所有合數,找到所有質數。

質數有無限多個,證明省略。我們無法找到所有質數,通常是預先訂立一個範圍,只找到範圍內的所有質數。

欲刪掉質數i的倍數之時,早已刪掉1倍到i-1倍了,直接從i倍開始。

欲刪掉質數i的倍數之時,早已刪掉「小於i的質數、其倍數」倍了,直接刪掉「大於等於i的質數、其倍數」倍。

乍看下程式碼增多而變慢,實際上cache miss減少而變快。

一個合數x,必定有一個小於等於sqrt(x)的質因數。所有小於等於sqrt(x)的質數,刪掉這些質數的倍數,就能刪掉所有合數了。

顛倒true和false,節省初始化時間。

製作質數表。篩法結束之後,掃描一次陣列即可。

UVa 406 516 524 543 10140 10311 11408

使用bitset來取代bool陣列

一個int有32個位元,可以當作32個欄位來使用,節省記憶體空間,減少cache miss。

不處理2的倍數

不處理2的倍數,節省一半記憶體,增進一點速度。

令陣列第0格代表數字1、陣列第1格代表數字3、陣列第2格代表數字5、……,以此類推。

時間複雜度

考慮內層迴圈索引值j一共有多少種:(N/2 - 2) + (N/3 - 3) + (N/5 - 5) + ... + (N/sqrtN - sqrtN) = O(NloglogN)。

1/1 + 1/2 + 1/3 + ... + 1/N     = O(logN)
1/2 + 1/3 + 1/5 + ... + 1/N     = O(loglogN)
1/2 + 1/3 + 1/5 + ... + 1/sqrtN = O(loglogsqrtN) = O(loglogN)
http://en.wikipedia.org/wiki/Divergence_of_the_sum_of_the_reciprocals_of_the_primes
1/1 + 1/2 + 1/3 + ... + 1/n - ln(n)     趨近於Euler-Mascheroni constant
1/2 + 1/3 + 1/5 + ... + 1/n - ln(ln(n)) 趨近於Meissel-Mertens constant

Prime Generation: Segmented Sieve of Eratosthenes

Segmented Sieve of Eratosthenes

篩法當中,以不大於sqrtN的質數,篩選大於sqrtN的數。

篩法需要大量記憶體空間。為了節省記憶體空間,於是有了分段處理的手法:一、首先求得不大於sqrtN的質數。二、將記憶體切成小段,每段長度sqrtN。分別篩選每一段。

空間複雜度從O(N)變成O(sqrtN),大幅減少cache miss。

也許可以作為平行演算法的經典範例。

Prime Generation: Linear Sieve Algorithm

線性時間篩法

一邊製作質數表,一邊刪掉每個數的質數倍。每個合數只遇到最小質因數(次小因數),每個合數只讀取一次。時間複雜度O(N)。

Twin Prime Conjecture

Twin Prime Conjecture

孿生質數猜想。相鄰兩個質數,差距等於2,有無限多組?

UVa 10394