Tanky WooRSS

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/)