埃拉托斯特尼筛法证明_eratosthenes筛法

下面我们以求出素数个数为例来说明埃氏筛法。

1、过程：先将N个自然数按次序列排列起来。1不是素数，也不是合数，划去。2是素数需要留下，而所有的偶数都要划去。3是素数留下，而所有3的倍数全部划去…以此类推，如果把所有素数的倍数全部划去，则所有留下的数就都是素数了。

2、时间复杂度：O(nlog(logn));

3、要筛选找到n为止的所有素数，则仅对不超过n^(1/2)（即对n的算术平方根以内）的素数进行筛选即可。

为什么只需要筛选到n^(1/2)内的素数：

因为如果一个数不是素数，那么它一定可以分解成两个自然数的乘积，其中至少一个小于或等于它的平方根，所以如果已经筛选出了小于或等于n的平方根的所有素数，那么剩下的数中必定没有小于或等于n的平方根的因子，说明剩下的数都为素数。

只筛选奇数：显然所有的偶数都是2的倍数，即所有的偶数都不是素数。

4、程序：

#include <stdio.h>
#include <stdbool.h>
#define N 10000
bool isprime(int n)
{
	int i;
	for(i=2;i*i<=n;i++)
	{
		if(n%i==0) return true;//若是合数，则输出true
	}
	return false;//若是素数，则输出false
}

bool a[N+1]={false};//要求N内的素数个数，定义数组的范围比N大1，防止出现越界
//全局定义a[],默认所有数都为素数，即全为flase

int main()
{
	int i, j;
	for(i=3;i*i<=N;i+=2)//从3开始，筛选出前n的平方根内的所有素数
	//i+=2，所有的偶数都不是素数，故不进行考虑
	{
		if(isprime(i)==true) continue;
		//若i为合数，则不用进行下一步的划去i的倍数
		for(j=i*i;j<=N;j=j+i*2)
			//从i的平方开始进行筛除，一直到N，将所有的i的倍数全部赋值为true
			//即判断合数。
			//步长为i*2，可以在一定程度上减少重复的筛选，但不能完全消除重复筛选
		{
			if(a[j]==false) a[j]=true;
		}
	}//至此，N内的所有素数均在数组中为0，而合数均为1
	int cnt=0;//cnt作为记录素数的个数
	for(i=3;i<=N;i+=2)
	{
		if(a[i]==false) cnt++;
		//从3开始判断，若a[i]为false，则记录素数的个数+1
	}
	if(N<2) cnt=0;//如果是1以内，则没有素数
	if(N>=2) cnt++;//2也为素数，故素数的数目需要加上1
	printf("%d\n", cnt);
	//若要输出所有的素数，则如下:
	if(N<2) printf("没有素数");
	if(N>=2) printf("2\n");
	for(i=3;i<=N;i+=2)
	{
		if(a[i]==false) 
		{
			printf("%d\n", i);
		}
	}
	return 0;
}

今天的文章埃拉托斯特尼筛法证明_eratosthenes筛法分享到此就结束了，感谢您的阅读。