[C Programming] 求質數-延伸

請參見求質數問題。
延伸問題：
1. 跳過2、3、5的倍數也是可能的，試構想作法並說明其複雜程度，
    以及是否值得寫到程式中？
2. 程式中把5放到prime[]中，是否為多此一舉？為什麼？
    不這樣做的話，有沒有什麼好的替代方案？
3. 有人說，is_prime這個變數是多餘的，其實也是如此，
    你有沒有辦法修改這個程式讓它不需要用is_prime呢？
    程式會比較容易讀嗎？
4. 修改程式讓它可以求出1~N(使用者輸入)中的所有質數。
    請問如果程式再改成讀入M與N(M<N)，
    求出M到N之間的所有質數時，程式的工作量可以少一點嗎？
    為什麼？

個人解答：
1. 考慮到5的倍數的話，
    為: 30n+1、30n+7、30n+11、30n+13、30n+17、30n+19、30n+23、30n+29
    間隔差距為：6 4 2 4 2 4 6 2 的循環，我們可以定一個dist的陣列：
    dist[8] = {6,4,2,4,2,4,6,2};
    前面的數為2、3、5、7，distCnt = 1，
    接下來每次遞增distCnt，用除以8的餘數來達到間距切換的目的。
    也就是每30個數裡面要判斷8個，
    這和原先的每6個數裡面要判斷2個比較起來，
    每經過30個數，我們就可以少判斷2個。

Code：

int* nAdvPrime(int n)
{
 int *prime = (int*)malloc(sizeof(int)*n);
 int i, isPrime, distCnt = 1, totalCnt = 4, primeCand = 7;
 prime[0] = 2; prime[1] = 3; prime[2] = 5; prime[3] = 7;
 int dist[8] = {6,4,2,4,2,4,6,2};
 // isPrime: 1 -> TRUE, 0 -> FALSE.
 while(totalCnt < n)
 {
  primeCand += dist[(distCnt++)%8];
  isPrime = 1;
  for( i = 0; prime[i]*prime[i]<=primeCand; i++ )
   if(primeCand % prime[i] == 0)
   {
    isPrime = 0; break;
   }
  if(isPrime) 
   prime[totalCnt++] = primeCand;

 }
 return prime;
}

2. 5先放到prime[]裡可以節省一點時間，認真說起來，
    我們是可以從5開始檢查，但比較浪費而已。
3. is_prime可以視作是多餘的，我們可以在迴圈結束的時候，
    再次以if(!primeCand % prime[i] == 0)來檢查，成立的話就是質數，
    這樣就不需要用到is_prime。每輪會少掉兩個指定is_prime值的操作，
    但會多出一次求餘數的檢查。(而且也比較不好理解)
    或者，我們可以把for迴圈的部分寫成一個小函式，
    在確認為合成數的時候直接return 0，或者迴圈跑到最後發現是質數的話，
    就return 1。這樣我們可以直接寫成if(funcIsPrime(...))的形式，
    程式碼會更好讀，唯一不確定的就是這樣再度呼叫函式的速度會不會受影響。
4. 求出1~N(使用者輸入)中的所有質數時，只要把while迴圈的條件改成：
    primeCand <= N，然後陣列的大小開成(N*8)%30 + 2即可，
    因為以30的倍數來看，除第一個循環外，每30個數最多有8個數有可能是質數，
    而第一輪有10個質數(2,3,5,7,11,13,17,19,23,29)，所以多加上2。

    求出M到N之間的所有質數時，程式的工作量沒辦法變少，
    因為還是要把這之前的質數找出來。