1554: 蓝桥杯算法提高VIP-素数求和（筛法合集）

解题思路:

基本的筛法有三种，普通筛法、埃氏筛法和欧拉筛法，他们的时间复杂度分别是O(n^2),O(nlognlogn),O(n)

这里将依次给大家介绍它们的原理和代码实现。

一、普通的筛法

我们知道，质数的定义就是他的约数只有1和它本身，所以我们用从2开始到n-1的数依次对n取余，如果可以整除的话说明它不是质数。

对这个方法进行简单优化的话，可以从2开始只遍历到n½，我们可以来简单证明一下：
对于一个合数，那么一定可以由两个自然数相乘得到， 其中一个大于或等于它的平方根，一个小于或等于它的平方根，并且成对出现。

因为是成对出现的，所以我们遍历完它小于等于平方根的数以后，就可以结束了。

c语言提供了开方函数，sqrt()，它在头文件<math.h>中。

题目的数据规模是两百万，如果时间复杂度是O(n^2)的话，运算次数最大可以到四万亿，远大于10^8，而经过简单优化后的时间复杂度是O(n^（3/2）)，大概是二十八亿左右，提交代码后运行了600毫秒，勉强过关。

代码如下：

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

int ff(int n){
	if(n<=1)return 0;
	int i;
	for(i=2;i<=sqrt(n);i++){//注意这里的=，平方根*平方根也是一种情况
		if(n%i==0)return 0;//如果可以整除立即返回
	}
	return 1;
}

int main ()
{
	int i,j,k=0;
	int n=0,m=0;
	long long int z=0;//考虑到数据规模过大，使用long long 型
	scanf("%d",&n);
	for(i=2;i<=n;i++){
		if(ff(i)==1){
			z+=i;
		}
	}
	printf("%lld",z);
	
	return 0;
}

二、埃氏筛法

埃氏筛法需要先建立一个数组，i从2开始到sqrt(n)，如果p[i]没有被标记成1的话，我们就把i的倍数全部删掉（即为标记成1），以n=20为例

第一次循环，p[2]没有被标记，所以我们要删掉2的倍数，即为p[4]=1,p[6]=1……

第二次循环，p[3]没有被标记，所以我们要删掉3的倍数，即为p[6]=1,p[9]=1……

第三次循环，p[4]被标记了，跳过再看下一个p[5]，p[5]没有被标记，所以删掉5的倍数……

一直循环到i=sqrt(n)，没有被标记的就是质数了。

数学描述就是：要得到自然数n以内的全部素数，必须把不大于根号n的所有素数的倍数剔除，剩下的就是素数。

它的时间复杂度是O(nlognlogn)，因为2的倍数有6，3的倍数也有6，6就会被重复删两次，这种重复删除造成了lognlogn的出现

代码实现如下：

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

int p[2000001];//注意最后要有1，不然没有办法得到2000000的值

int ff(int n){
	int i,j;
	for(i=2;i<=sqrt(n);i++){//遍历到根号下n即可
		if(p[i]==0){
			for(j=i+i;j<=n;j+=i){//找到i的倍数
				p[j]=1;
			}
		}
	}
}

int main ()
{
	int i,j,k=0;
	int n=0,m=0;
	long long int z=0;
	scanf("%d",&n);
	ff(n);
	for(i=2;i<=n;i++){
		if(p[i]==0){
			z+=i;
		}
	}
	printf("%lld",z);
	
	return 0;
}

三、欧拉筛法

欧拉筛法又称线性筛，埃氏筛法筛掉的是质数的倍数，而线性筛筛掉的是i与已经找到的质数的乘积。

线性筛需要两个数组，第一个和埃氏筛法的用途一样，用来判断是否为质数，而第二个用来存放已经找到的质数。

第二个数组的大小不用开的和第一个一样大，在数论领域有一个判断质数个数的近似公式，π（n）=n/ln(n)，带入2000000大概是十三万左右，考虑到存在误差，数组开二十万就可以了。

看代码：

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

int p[2000001];
int x[200000];

int ff(int n){
	int i,j,k=0;
	for(i=2;i<=n;i++){
		if(p[i]==0){
			x[k++]=i;//将找到的质数放入数组
		}
		for(j=0;j<=k&&x[j]*i<=n;j++){//j>k超过已经存放的质数，x[j]*i>n超过要求的范围
			p[x[j]*i]=1;        //x[j]是已经找到的质数，与i相乘是一个合数，所以删去
			if(i%x[j]==0){//核心代码
				break;
			}
		}
	}

}

int main ()
{
	int i,j,k=0;
	int n=0,m=0;
	long long int z=0;
	scanf("%d",&n);
	ff(n);
	for(i=2;i<=n;i++){
		if(p[i]==0){
			z+=i;
		}
	}
	printf("%lld",z);
	
	return 0;
}

需要注意的就是核心代码，这个是欧拉筛是线性筛的关键，它保证了每个合数只会被筛一次。

每个合数只被它的最小质因数筛去，以40为例：

40=2*20=4*10=5*8；

它的最小质因子是2，当i等于20的时候才会被删去，如果i=8，还没有等到5*8，在x[j]=2的时候就break跳出循环了。

具体大家可以演算一下，就能体会到它的魅力了。

因为每个合数只筛一次，所以欧拉筛做到了线性筛的时间复杂度，基本在20毫秒内就完成了运算。

不过埃氏筛法和欧拉筛的空间复杂度很大，这也算是以空间换时间了。

到这里三种筛法的介绍就结束了，埃氏筛法和欧拉筛的数学原理需要大家自己查看具体论文了，以后再来查漏补缺吧。

以上。