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

最近更新时间:2011.10.8


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

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

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

若用vis[i]==1表示已被删除,则代码如下:
—————————————————–
代码一:

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

上面的代码效率已经很高了。
但还可以继续优化。
看一个改进的代码:
——————————————————
代码二:

1
2
3
4
5
6
7
8
9
10
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是从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. ------------------------------------------------------ 这里用代码二给大家一个完整的代码:

//版本二
//Author: Tanky Woo
//Blog: www.wutianqi.com
 
#include <stdio.h>
#include <string.h>
#include <math.h>
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/)


发布者

Tanky Woo

Tanky Woo,[个人主页:https://tankywoo.com] / [新博客:https://blog.tankywoo.com]

《The Sieve of Eratosthens(爱拉托逊斯筛选法)》有11个想法

发表评论

电子邮件地址不会被公开。 必填项已用*标注