題目來源 : Prime Cuts
解題 :
常見的質數題目，一般來說都會用到埃氏篩法(Sieve of Eratosthenes)來找出質數。
首先，我建立一個prime -- 大小為n的一維boolean陣列，代表某數字是否為質數。
埃氏篩法(Sieve of Eratosthenes)作法如下 :
若一個正整數為另一個正整數的倍數，則這個整數必定不是質數。
所以，從最小質數2開始，將所有2的倍數(不包含2)標記為⌈非質數⌋。
接著，往下下一個沒有被標記成質數的數字3，再將3的倍數(不包含3)標記為⌈非質數⌋。
以此類推下去，直到找出所有小於等於n的質數。
找出所有質數後，只要根據質數的數量，並且依找題目要求輸出中間2*C (或是 2*C - 1)個質數
沒有留言:
張貼留言