厄拉多塞筛算法实现

一、描述：

从 1到N 如果找到一个数 a是素数，那么将2*a 3*a .....M*a (M*a一直到没有剔除为止：这样剩下的数就都是素数了。 一個大於1的整數，如果除了它本身和1以外，不能被其他正整數所整除，這個整數就叫質數質數也叫素數，如2、3、5、7、11、13…..都是質數。

如何從正整數中把質數挑出來呢？自然數中有多少質數？人們還不清楚，因為它的規律很難尋找，他像一個頑皮的孩子一樣，東躲西藏，和數學家玩捉迷藏。

1	2	3	4	5	6	7	8	9	10
11	12	13	14	15	16	17	18	19	20
21	22	23	24	25	26	27	28	29	30
31	32	33	34	35	36	37	38	39	40
41	42	43	44	45	46	47	48	49	50

 

厄拉多塞篩法

西元前250年，希臘數學家、亞歷山大圖書館館長厄拉多塞(Eeatosthese)想到了一個非常美妙的質數篩法，減少了逐一檢查每個數的的步驟，可以比較簡單的從一大堆數字之中，篩選出質數來，這方法被稱作厄拉多塞篩法(Sieve of Eeatosthese)。
以上表為例，2是質數，以2為篩子，留下2並刪去2的倍數;2之後未被刪去的第一個數是3，它是質數。以3為篩子，留下3並刪去3的倍數;3之後未被刪去的第一個數是5，它是質數。以5為篩子，留下5並刪去5的倍數;5之後未被刪去的第一個數是7，它是質數。以7為篩子，留下7並刪去7的倍數;7之後未被刪去的第一個數是11，它是質數。到此就算完成尋找所有介於1和50之間的質數，因為50的平方根大於7而且小於8，現在表格所剩的數字都是質數。

二、实现

#include <stdio.h>

int Eeatosthese(int N)
{
  int i, j, a[N];

  for (i = 2; i < N; i++) a[i] = 1;
  for (i = 2; i < N; i++)
    if (a[i])
      for (j = i+i; j < N; j += i)
        a[j] = 0;
 

  for (i = 2; i < N; i++)
    if (a[i]) printf("%4d ", i);
  printf("\n");
}