素数表获取的朴素算法与埃氏筛法

朴素算法

可以先来看看一道简单的题目：
试打印 1 - n 范围内的素数表。
分析：
好，我们从1~n进行枚举，判断每个素数是否是素数，如果是素数，则加入素数表。那么这个算法的时间复杂度是多少呢？可以看到，枚举部分的复杂度是O(n)，而判断素数的算法是O(n^1/2)，因此总复杂度是O(n * n ^1/2)。但是显然这个复杂度对n超过10 ^ 5的情况来说是有问题的。因为对一般的oj系统来说，一秒能承受的运算次数大概是10 ^ 7 ~ 10 ^ 8，而程序一般要求1s内进行。自己可以估算一下。
给出代码（以求解100以内的所有素数为例）：

#include<stdio.h>
#include<math.h>

bool isPrime(int n){//判断n是否为素数 
	if(n<=1)return false;
	int sqr = (int)sqrt(1.0*n);
	for(int i = 2;i<=sqr;i++){
		if(n%i==0)return false;
	}
	return true;
}

int prime[101],pNum = 0;//prime[]数组存放素数，pNum为数组下标 
bool p[101] = {0};

void Find_Prime(){
	for(int i = 1;i<101;i++){
		if(isPrime(i) == true){
			prime[pNum++] = i;
			p[i] = true;
		}
	} 
}

int main(){
	Find_Prime();
	for(int i = 0;i<pNum;i++){
		printf("%d ",prime[i]);
	}
}

埃氏筛法

好，我们接着上面讲的继续讲下去，既然朴素算法的时间复杂度不是很令人满意，那么是否有更好的算法呢？
“埃氏筛法”就是众多筛法中简单的一种，可以达到O(nloglogn)的时间复杂度。所谓“筛法”关键就在于一个筛字。从小到大枚举所有数，对每一个素数，筛去它的所有倍数，剩下的都是素数了。这听起来好像是在逗人？？？你还不知道哪个数是素数呢，简直就是悖论。
先来看一个例子吧：求1~15中的所有素数。

• 2是素数（唯一需要事先确定），因此筛去所有2的倍数，即2，4，6，8
• 3没有被前面的步骤筛去，因此3是素数，筛去所有3的倍数，即6，9，12，15。
• 4已经被步骤1筛去，因此4不是素数
• 5没有被前面的数筛去，因此5是素数，筛去所有5的倍数，即10、15
• 6被筛去，不是素数
• 7没有被筛去，是素数，筛去7的倍数：14
• 8被筛去，不是素数
• 9被筛去，不是素数
• 10被筛去，不是素数
• 11没被筛去，是素数
• 12被筛去，不是素数
• 13没被筛去，是素数
• 14被筛去，不是素数
• 15被筛去，是素数
  至此，1~15内的所有素数都已得到，即2、3、5、7、11、13。
  由上面的例子可以发现，当从小到大到达某数a时，如果a没有被前面步骤的数筛去，那么a一定是素数。这是因为，如果a不是素数，那么a一定有小于a的素因子，这样在之前的步骤中a一定会被筛掉，所以，如果当枚举到a时还没有被筛掉，那么a一定是素数。

分析：
至于“筛”这个动作的实现，可以使用一个bool型数组p来标记，如果a被筛掉，那么p[a]为true，否则，p[a]为false。在程序开始时可以初始化p数组为false。
给出上述题目的代码（埃氏筛法）：

#include<stdio.h>

const int maxn = 101;
int prime[maxn], pNum = 0;
bool p[maxn] = {0};
//初始化p数组全部为false,如果a被筛掉,那么p[a]为true;否则,p[a]为false 

void Find_Prime(){
	for(int i = 2;i<maxn;i++){
		if(p[i] == false){//p[i] == false说明i是素数,那么就把此数i存到prime数组中 
			prime[pNum++] = i;
			for(int j = i+i;j<maxn;j+=i){
				//筛去i的所有倍数 
				p[j] = true;
				//i的所有倍数对应的p[i]设置为true,这样就不会存到prime数组中 
			}
		}
	}
}

int main(){
	Find_Prime();
	for(int i = 0;i<pNum;i++){
		printf("%d ",prime[i]);
	}
} 

最后留道题目供练习：

令Pi表示第 i 个素数，现任意给两个正整数M<=N<=10^4，请输出PM到PN的所有素数。
输入格式：
输入在一行中给出M和N，其间以空格分隔。
输出格式：
输出从PM~PN的所有素数，每10个数字占一行，其间以空格分隔，但行末不能有空格。
给出代码（埃氏筛法和朴素都可以，这里给出的是埃）：

//埃氏筛法 
#include<stdio.h>

const int maxn = 1000001;
int prime[maxn], num = 0;
bool p[maxn] = {0};
//初始化p数组全部为false,如果a被筛掉,那么p[a]为true;否则,p[a]为false 

void Find_Prime(int n){
	for(int i = 2;i<maxn;i++){
		if(p[i] == false){//p[i] == false说明i是素数,那么就把此数i存到prime数组中 
			prime[num++] = i;
			if(num>=n)break;//只需要n个素数,超过时就退出 
			for(int j = i+i;j<maxn;j+=i){
				//筛去i的所有倍数 
				p[j] = true;
				//i的所有倍数对应的p[i]设置为true,这样就不会存到prime数组中 
			}
		}
	}
}

int main(){
	int m,n,count = 0;
	scanf("%d %d",&m,&n);
	Find_Prime(n);
	for(int i = m;i<=n;i++){
		printf("%d",prime[i-1]);
		count++;
		if(count%10!=0&&i<n)	
			printf(" ");
		else printf("\n");
	}
	return 0;
}