The Sieve of Eratosthens

爱拉托逊斯筛选法

（原创链接：http://www.wutianqi.com/?p=264）

思想：对于不超过n的每个非负整数P，删除2P, 3P…，当处理

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

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

—————————————————–

代码一：

1memset(vis,0,sizeof(vis));

2for(inti=2; i<=100; i++)

3for(intj=i*2; j<=100; j+=i)

4 vis[j]=1;

上面的代码效率已经很高了。

但还可以继续优化。

看一个改进的代码：

——————————————————

代码二：

1intm=sqrt(double(n+0.5));

2

3for(inti=2; i<=m; i++)

4if(!vis[i])

5{

6 prime[c++]=i;

7for(intj=i*i; j<=n; j+=i)

8{

9 vis[j]=1;

10 }

11 }

——————————————————

先分析代码一：

这个代码就是简单的将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.

------------------------------------------------------

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

1//版本二

2//Author: Tanky Woo

3//Blog: www.wutianqi.com

4

5#include<stdio.h>

6#include<string.h>

7#include<math.h>

8intvis[100];

9intprime[100];

10intc=0;

11intn;

12intmain()

13{

14 scanf("%d",&n);

15intcnt=1;

16

17 memset(vis,0,sizeof(vis));

18intm=sqrt(double(n+0.5));

19

20for(inti=2; i<=m; i++)

21if(!vis[i])

22{

23 prime[c++]=i;

24for(intj=i*i; j<=n; j+=i)

25{

26 vis[j]=1;

27//printf("%d\n", j);

28}

29 }

30

31for(inti=2; i<n; i++)

32{

33if(vis[i]==0)

34{

35 printf("%d", i);

36 cnt++;

37if(cnt%10==0)

38 printf("\n");

39 }

40 }

41 printf("\ncnt = %d\n", cnt);

42return0;

43}

完毕。

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

原文链接: https://www.cnblogs.com/tanky_woo/archive/2010/08/04/1792119.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍