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

（原創(chuàng)鏈接：http://www.wutianqi.com/?p=264）
思想：對(duì)于不超過n的每個(gè)非負(fù)整數(shù)P，刪除2*P, 3*P…，當(dāng)處理

完所有數(shù)之后，還沒有被刪除的就是素?cái)?shù)。

若用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;

上面的代碼效率已經(jīng)很高了。
但還可以繼續(xù)優(yōu)化。
看一個(gè)改進(jìn)的代碼：
——————————————————
代碼二：

 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    }

——————————————————
先分析代碼一：
這個(gè)代碼就是簡(jiǎn)單的將Eratosthenes篩選法描述出來。不用多說。
分析代碼二：
考慮幾點(diǎn)：
1.為何從i=2~m?
因?yàn)橄旅娴膉是從i*i開始的。
2.為何j從i*i開始？
因?yàn)槭紫仍趇=2時(shí)，偶數(shù)都已經(jīng)被刪除了。
其次，“對(duì)于不超過n的每個(gè)非負(fù)整數(shù)P”， P可以限定為素?cái)?shù)，
為什么？
因?yàn)椋?i 執(zhí)行到P時(shí)，P之前所有的數(shù)的倍數(shù)都已經(jīng)被刪除，若P

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

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

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

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

 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}

完畢。