PRIME1 - Prime Generator
PRIME1 - Prime Generator
題目敘述：
Peter wants to generate some prime numbers for his cryptosystem. Help him! Your task is to generate all prime numbers between two given numbers!
INPUT:
INPUT:
The input begins with the number t of test cases in a single line (t<=10). In each of the next t lines there are two numbers m and n (1 <= m <= n <= 1000000000, n-m<=100000) separated by a space.
OUTPUT:
OUTPUT:
For every test case print all prime numbers p such that m <= p <= n, one number per line, test cases separated by an empty line.
題目解析：
要求先輸入一整數，為接下來要輸入的資料組數，接著輸出每組輸入的兩數字中間的 Prime Number 。難度不高，但在CPE等程式能力檢定考試內，是非常常出現的送分題。
練習重點：pair、queue、質數偵測演算法
開始實作：
第一個輸入的變數 t 決定了總共要處理多少組資料，而每一組資料分別有 m、n 作為等等要尋找 Prime Number p 的依據，在題目裡面有關於 t<=10, 1 <= m <= n <= 1000000000, n-m<=100000 的限制，為審理系統將會輸入的默認規則，基本上不用特意寫防呆機制，但如果有心還是可以自行補上。要注意的是1 <= m <= n <= 1000000000，我們必須確定 m、n 都還是在 integer 的範圍內，如果有超過的情況，那就要根據情況做變化，不能只用 integer 做為唯一的承接資料型態，不過這邊是沒有超過的，所以暫時不用考慮那麼多。
現在程式已經能輸入 t 組 pair 資料了，那接下來要處理 18 行那裏對 Prime Number 的尋找。
如果只是單純用定義來寫的話，那「數字沒有比除了 1 還有自己以外的因數」是不難寫出來的概念，只要用一個 for 來跑一到那個數字的範圍，看有沒有其中的數字是被除後餘零( 整除，因數 )，就可以知道是不是 Prime Number 了。
為了提升效率，我們必須加入一點小改動讓程式跑的較為快速一點，考慮清楚有那些情況是不用重複跑的，舉例來說，假設我要判斷 1000 是不是一個質數，那我是否必須 2 ~ 999 都跑一次才可知道？當然，這個例子在跑到 2 的時候就會判定有 1 和自己以外的因數，並判斷此數字並非質數。
但假設如果這個我們選定的數字剛剛好是質數，那就要一直跑到 999 確定了都沒有因數才會結束迴圈判定過程，那麼在已經跑過 2 的情況下還不斷去跑諸如 4、6、8 這類已經確定不會是因數的偶數呢?同理可以套用到 3 或是 5 之類前幾個已知質數。
另外，這個部分應該比較多人知道，就是要測驗是否有因數可以被剛好整除，這個測試只要試到被測試數的開更號就好，因為再上去也只是前面測過的補數而已。
綜上所述，理論上來說如果手邊有一個全質數表的陣列，就可以做出一個超高速的質數偵測程式，不過理論終究是理論，如果要偵測的數已經大到一個程度，那質數表可能就跟不上我們的所需了，並且，要儲存一概括所有質數的陣列所需記憶體也會變得非常龐大。
這樣的寫法會被C++入門測試接受，不過修過資料結構和演算法的不應該只滿足於此，應該要去探討和優化。簡單的優化：在第七行後面加一個 if 判斷式，if ( n % 2 == 0 )return false ; ，並在第九行的 for 那裡重寫成 for ( int i = 3 ; i <= sqrtN ; i += 2 ){，這樣的寫法可以在被測數為基數的情況下繞過近乎一半的待測數字。
當然直接照搬一個質數表進來不是不可以，但在記憶體上會佔比較大空間，所以還是看情況，看我們要測試的資料組分布是多大，如果待測數大小沒有大到一個程度，那測試 2 的倍數應該就差不多了。
2.接下來就牽涉到演算法的東西了，之後再補上...
留言
張貼留言