Tanky Woo / RSS

The Sieve of Eratosthens(爱拉托逊斯筛选法)

03 Jul 2010
这篇博客是从旧博客 WordPress 迁移过来，内容可能存在转换异常。

最近更新时间：2011.10.8

The Sieve of Eratosthens 爱拉托逊斯筛选法 思想：对于不超过n的每个非负整数P，删除2P, 3P...，当处理

完所有数之后，还没有被删除的就是素数。

若用vis[i]==1表示已被删除，则代码如下：

代码一：

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

上面的代码效率已经很高了。 但还可以继续优化。

看一个改进的代码：

代码二：

int m = sqrt(double(n+0.5));

for(int i = 2; i <= m; i++)
    if(!vis[i])
    {
        for(int j = i*i; j <= n; j += i)
        {
            vis[j] = 1;
        }
    }

先分析代码一： 这个代码就是简单的将Eratosthenes筛选法描述出来。不用多说。 分析代码二： 考虑几点： 1.为何从i=2~m? 因为下面的j是从ii开始的。 2.为何j从ii开始？ 因为首先在i=2时，偶数都已经被删除了。 其次，“对于不超过n的每个非负整数P”， P可以限定为素数， 为什么？ 因为，在 i 执行到P时，P之前所有的数的倍数都已经被删除，若P

没有被删除，则P一定是素数。 而P的倍数中，只需看： (p-4)p, (p-2)p, pp, p(p+2), p(p+4) （因为P为素数，所以为奇数，而偶数已被删除，不需要考虑p(p

-1)等）（Tanky Woo的程序人生） 又因为(p-4)p 已在 (p-4)的p倍中被删去，故只考虑： pp, p(p+2)....即可 这也是i只需要从2到m的原因。 当然，上面 pp, p*(p+2)...的前提是偶数都已经被删去，而代码

二若改成 j += 2i ,则没有除去所有偶数，所以要想直接 加2i

。只需在代码二中memset()后面加： for(int i = 4; i <= n; i++) if(i % 2 == 0) vis[i] = 1;

这样，i只需从3开始，而j每次可以直接加 2*i.

这里用代码二给大家一个完整的代码：

//版本二
//Author: Tanky Woo
//Blog: www.wutianqi.com

#include 
#include 
#include 
int vis[100];
int n;
int main()
{
    scanf("%d", &n;);
    int cnt = 1;

    memset(vis, 0, sizeof(vis));
    int m = sqrt(double(n+0.5));

    for(int i = 2; i <= m; i++)
        if(!vis[i])
        {
            for(int j = i*i; j <= n; j += i)
            {
                vis[j] = 1;
                //printf("%d\n", j);
            }
        }

    for(int i = 2; i < n; i++)
    {
        if(vis[i] == 0)
        {
            printf("%d ", i);
            cnt++;
            if(cnt % 10 == 0)
                printf("\n");
        }
    }
    printf("\ncnt = %d\n", cnt);
    return 0;
}

完毕。

欢迎大家和我交流。(我的博客:http://www.wutianqi.com/)

京ICP备16016622号