素数筛选法

素数，是指因子只包含1和其本身的数，那么，我们怎么判断素数呢？

（以下代码均基于打表（1~1e6）的基础上完成）

1.按照定义计算

素数的定义就是一个数的因子只包含1和其本身，那么我们直接就按照定义写：

#include<stdio.h>
#include<string.h>
#define maxn 1000000+10
int pri[maxn];
int isprime(int n)
{
	for(int i=2;i<n;i++)
		if(n%i==0)
			return 0;
	return 1;
}
int main()
{
	pri[1]=0;
	for(int i=2;i<=maxn;i++){
		pri[i]=isprime(i);
	}
	return 0;
}

这是最基础的写法，也是最小白的写法。毕竟，当时我刚高一加入大学的某个协会时，考的就有判断素数...

这种算法的复杂度为O(n^2),复杂度非常的大，对于1e6的数据范围来说肯定要超时，那么还有没有更优化的算法？答案是肯定的

 

2.基于定义计算的优化算法

我们对一个合数进行考虑，例如12：

它的因子有1 2 3 4 6 12 ，而且1*12=12 ，  2*6=12 ， 3*4=12

可见，每一个因子都会有另一个对应的因子，观察可得，它们的分布是平均的，左边的一半对应右边的一半，那么最中间的分界线应该是什么？ √n 。

因此，我们只需要对√n 前面的数字进行判断即可。

#include<stdio.h>
#include<string.h>
#define maxn 1000000+10
int pri[maxn];
int isprime(int n)
{
	for(int i=2;i*i<=n;i++)//只需要将i变成i*i即可 
		if(n%i==0)
			return 0;
	return 1;
}
int main()
{
	pri[1]=0;
	for(int i=2;i<maxn;i++){
		pri[i]=isprime(i);
	}
	return 0;
}

这种算法的复杂度要比上一种好的多，复杂度为O(n√n),但是对于1e6的数据范围来说还是太大了。有没有再快一点的算法？

3.素数筛选法

素数筛选法的思想为：

从2开始，因为2的倍数一定不是素数，所以先把2的倍数全部删去；

接着找下一个素数3，把3的倍数全部删去；

因为4是2的倍数，已经被删去，所以直接找下一个素数5，把5的倍数全部删去；

接着7的倍数，11的倍数，......直到把1e6范围内的合数全部筛选出去，剩下的即为素数：

//以下优化均基于打表的基础上
 
#include<stdio.h>
#include<string.h>
#define maxn 1000000+10
int vis[maxn];
void isprime()
{
	memset(vis,0,sizeof(vis));//此处vis[i]=1表示不是素数，vis[i]=0表示是素数 
	vis[1]=1;
	//由于i*i的数据范围可能会超过int，所以需要用long long表示
	for(long long i=2;i*i<=maxn;i++){//此处有优化，因为如果一个合数>sqrt(maxn),那么他必定在前面已经被标记过。 
		if(!vis[i]){
			for(long long j=i*i;j<=maxn;j+=i){//此处也有优化，我们只需要判断从i*i开始判断即可。 
				vis[j]=1;
			}
		}
	}
}
int main()
{
	int n;
	isprime();
	return 0;
}

这种算法的复杂度应该为O(n);，是一种非常快速的判断素数的算法。

上述代码有两处优化，第一处优化的证明如下：

假设 maxn > i > sqrt(maxn)并且为合数，那么，他肯定会有一个因子小于等于sqrt(maxn)，因此，i一定在之前已经被标记过了。

第二处优化证明为：

假设i>2，那么对于 i * ( i - 1 )：

如果 i - 1是素数，那么 i * ( i - 1 ) 一定在之前已经被标记过；

否则，如果 i - 1 是合数，那么  i - 1能被分成更小的素数。设其中一个为a，那么 i * ( i - 1 )= i * ( i - 1 ) / a * a 也一定被标记过。

优化后的算法时间会节省非常多，在平常的算法竞赛中，用上述代码就已经可以解决大部分的涉及素数打表的问题。