Download presentation
Presentation is loading. Please wait.
1
10394: Twin Primes ★★★☆☆ 題組：Problem Set Archive with Online Judge
解題者：經皓元 解題日期：2013年5月2日 題意：twin prime為相差2的質數對，如(3, 5), (5, 7)…等。題目輸入一個整數S, 1<=S<=100,000 ，輸出第S對質數對。
2
題意範例： 1 (3, 5) (5, 7) (11, 13) 100,000 ( , ) 解法：建立質數表。因為第10萬對twin prime將超過1800萬, 若比較每個數是否能被其他數整除，將超過時限。 解法範例：以Sieve of Eratosthenes方法建立120以內的質數表作為範例。原理是消除所有的合數，剩下的就是質數。一個合數 x 必定有個小於等於 sqrt(x) 的質因數，若刪掉這些質數的倍數的倍數，就能刪掉所有合數了。 質數表建立完後掃過一遍建立twin prime表，之後依照 題目輸入輸出對應的twin prime。
7
從質數i的i倍開始消去的原因： 以7為例： 從7的7倍的倍數開始消去的原因： 7的2, 3, 5倍(質數倍)：已經在之前的質數的倍數中消掉。 7的4, 6倍(合數倍)：所有合數皆為小於它的質數的倍數，因此也在消去之前的質數的倍數中被消掉了。
9
判斷到質數7為止的原因： 120內的數若為合數，則必有一質因數小於等於sqrt(120) ≒ 10.95，因7為小於等於10.95中最大的質數，因此判斷到7就可以，之後沒有被消掉的數皆為質數。
10
討論： (1) 若用檢查因數的方法判斷質數，則時間複雜度為O(n^2) ，若改用Sieve of Eratosthenes判斷質數，時間複雜度變為O(n(logn)(loglogn))，以n = 2000萬來說，效率約差300萬倍
Similar presentations
