[C Programming] 求質數

請寫出一個程式，找出前N個(比如說200)個質數。
請使用除法的方法用最快的辦法來寫作程式。

解：
1. 質數的基本定義為除了1以及自己以外沒有其他的因數的數，
    就可以稱為質數。
2. 沒有其他因數的條件其實等同於沒有其他質因數，
    因為合成數可以拆成質數的乘積。
3. 另外，當某數x是合成數的話，那麼就會有x=i*j這樣的式子，
     i、j為x的因數；
     i、j要嘛就是一個大於根號x，一個小於根號x，
    不然就是兩個都等於根號x，因為兩者相乘必須要等於x，
    所以不能同時小於或同時大於根號x。
    所以我們只要找小於等於根號x的正整數中是否有x的因數，
    就可以確信x是否為質數。
4. 既然所有合成數都可以拆成質因數的乘積，
    當搜尋一個數是否為質數時，只要看它前面存在的質數，
    是否是它的因數，就可以判定了。
5. 有一些判斷是可以直接省略的，
    比如2的倍數，除了2以外，絕對不會是質數；
    同理，3的倍數也是相同，5的倍數也是。
    當考慮不是2的倍數和3的倍數時，
    剩下6n+1和6n+5兩種。
    考慮到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 的循環，但這比較麻煩，
    我們就先做6n+1和6n+5的循環，其他留待延伸題解決。
    這種循環的間隔為2、4、2、4......。
    觀察前面的質數：2 3 5 7 11不難發現可以從5到7這裡開始迴圈。
    由於只有兩種間隔，我們設定dist=2、增加到待檢數字後，
    用dist = 6-dist來變換，這樣就可以不停切換兩種間隔。

Code：

int* nPrime(int n)
{
 int *prime = (int*)malloc(sizeof(int)*n);
 int i, isPrime, dist = 2, totalCnt = 3, primeCand = 5;
 prime[0] = 2; prime[1] = 3; prime[2] = 5;
 // isPrime: 1 -> TRUE, 0 -> FALSE.
 while(totalCnt < n)
 {
  primeCand += dist;
  dist = 6-dist;
  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;
}

在main中:

int main(int argc, char *argv[])
{
 int i, n, *prime;
 scanf("%d", &n);
 printf("\n");
 prime = nPrime(n);
 for(i = 0; i < n; i++)
  printf("%4d: %d\n", i+1, prime[i]);
 system("PAUSE");
 return 0;
}