The Sieve of Eratosthens
愛拉托遜斯篩選法

（原創鏈接：http://www.wutianqi.com/?p=264）
思想：對于不超過n的每個非負整數P，刪除2*P, 3*P…，當處理

完所有數之后，還沒有被刪除的就是素數。

若用vis[i]==1表示已被刪除，則代碼如下：
—————————————————–
代碼一：

1memset(vis, 0, sizeof(vis));
2for(int i = 2; i <= 100; i++)
3    for(int j = i*2; j <= 100; j += i)
4        vis[j] = 1;

上面的代碼效率已經很高了。
但還可以繼續優化。
看一個改進的代碼：
——————————————————
代碼二：

 1int m = sqrt(double(n+0.5));
 2 
 3for(int i = 2; i <= m; i++)
 4    if(!vis[i])
 5    {
 6        prime[c++] = i;
 7        for(int j = i*i; j <= n; j += i)
 8        {
 9            vis[j] = 1;
10        }
11    }

——————————————————
先分析代碼一：
這個代碼就是簡單的將Eratosthenes篩選法描述出來。不用多說。
分析代碼二：
考慮幾點：
1.為何從i=2~m?
因為下面的j是從i*i開始的。
2.為何j從i*i開始？
因為首先在i=2時，偶數都已經被刪除了。
其次，“對于不超過n的每個非負整數P”， P可以限定為素數，
為什么？
因為，在 i 執行到P時，P之前所有的數的倍數都已經被刪除，若P

沒有被刪除，則P一定是素數。
而P的倍數中，只需看：
(p-4)*p, (p-2)*p, p*p, p*(p+2), p*(p+4)
（因為P為素數，所以為奇數，而偶數已被刪除，不需要考慮p*(p

-1)等）（Tanky Woo的程序人生）
又因為(p-4)*p 已在 (p-4)的p倍中被刪去，故只考慮：
p*p, p*(p+2)….即可
這也是i只需要從2到m的原因。
當然，上面 p*p, p*(p+2)…的前提是偶數都已經被刪去，而代碼

二若改成 j += 2*i ,則沒有除去所有偶數，所以要想直接 加2*i

。只需在代碼二中memset()后面加：
for(int i = 4; i <= n; i++)
if(i % 2 == 0)
vis[i] = 1;
這樣，i只需從3開始，而j每次可以直接加 2*i.
------------------------------------------------------
這里用代碼二給大家一個完整的代碼：

 1//版本二
 2//Author: Tanky Woo
 3//Blog: www.wutianqi.com
 4 
 5#include <stdio.h>
 6#include <string.h>
 7#include <math.h>
 8int vis[100];
 9int prime[100];
10int c = 0;
11int n;
12int main()
13{
14    scanf("%d", &n);
15    int cnt = 1;
16 
17    memset(vis, 0, sizeof(vis));
18    int m = sqrt(double(n+0.5));
19 
20    for(int i = 2; i <= m; i++)
21        if(!vis[i])
22        {
23            prime[c++] = i;
24            for(int j = i*i; j <= n; j += i)
25            {
26                vis[j] = 1;
27                //printf("%d\n", j);
28            }
29        }
30 
31    for(int i = 2; i < n; i++)
32    {
33        if(vis[i] == 0)
34        {
35            printf("%d ", i);
36            cnt++;
37            if(cnt % 10 == 0)
38                printf("\n");
39        }
40    }
41    printf("\ncnt = %d\n", cnt);
42    return 0;
43}

完畢。