[C Programming] 篩法

關於求質數，早在2000年前，
人們就知道了一個方法可以不必用除法，
就可找出從2到N之間的所有質數。
假設我們有一個很神奇的篩子，我們可以給它一個數i，
它可以把i的所有倍數去掉。
請用這個方法求出2到N之間的所有質數。

注意：
要求2到N的質數的話，最多篩到N/2就可以停下來了。
因為大過N/2的數都不可能整除N。
(因為存在這樣的數的話，表示有一個質數小於2且整除N)
程式不可使用乘法或除法，只能用加或減，以求加快速度。

這個方法叫做Eratosthenes(人名)的篩法(Sieve Method)。

解：
首先我們建立陣列，x[0] = 3、x[1] = 5、x[2] = 7......
(因為2的倍數可以直接不用考慮，或者說一開始就篩掉了)
所以x[i] = 2i+3 = i + i + 3。
我們可以用標記來表示x[i]是KEPT(保留，定為1)或DELETED(篩去，定為0)。
當一個一個查過去，沒有被篩掉的必然是質數，
因為其之前不存在任何數可以篩掉這個數。


接下來我們就要考慮碰到x[i]的時候，要篩掉2i+3的倍數：
1(2i+3)、3(2i+3)、5(2i+3)、7(2i+3)、9(2i+3)....(2n+1)(2i+3)  n=0,1,2,...
偶數的部分本來就不在裡面，
又因為自己不可以篩掉。
所以每次要增加2(2i+3)的值，
即陣列的索引值每次要增加2i+3。
我們依此來標記所有對應的索引值為篩去。
同時，如果只是要把範圍內的合成數篩掉而不計數，
理論上來說不需要篩到最後一個。這個部分留待延伸討論。
Code中其實可以用把KEPT和DELETED放在#define裡，
不過我不太喜歡這種用法，所以就算了XD

Code：

int Sieve(int* x, int n)
{
 // cnt = 1 because we don't have 2 in the array.
 int i, j, tmp, cnt = 1, KEPT = 1, DELETED = 0;
 for(i = 0; i <= n; i++)
  x[i] = KEPT;
 for(i = 0; i <= n; i++)
 {
  if(x[i])  // If KEPT -> start to sieve
  {
   tmp = i+i+3; // Each time index moves 2i+3
   cnt++;   // prime count
   for(j = i+tmp; j <= n ; j += tmp) 
    x[j] = DELETED;
  }
 }
 return cnt;
}

主程式部分：

int main(int argc, char *argv[])
{
 int i, k, count, n = 500;
 int *x = (int*)malloc(sizeof(int)*(n+1));
 count = Sieve(x, n);
 printf("Total: %d prime(s)", count);
 printf("\n%6d", 2);
 for(i = 0, k = 2; i <= n; i++)
 {
  if(x[i]) // KEPT
  {
   if(k > 10)
   {
    printf("\n");
    k = 1;
   }
   printf("%6d", 2*i+3);
   k++;
  } 
 }
 printf("\n");
 system("PAUSE");
 free(x); x = 0;
 return 0;
}