[数据结构与算法]算法：判断质数，从简单到高效

从小学起我们就接触过质数（素数），它也是我们日常写题过程中常见的一个要素。今儿咱就来唠唠怎么来判断素数

质数的定义：

质数是指在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数。

注意：最小的质数是2。

一、简单思维：

既然已经知道了质数的定义，很容易就想到根据定义来判断一个数是否为质数。

那么就来试一试吧！

方法（一）：直观判断

#include <iostream>
using namespace std;
//直观判断
//若n是质数，返回1；若n不是质数，返回0 。 
int judge1(int n)
{
	int i;
	//n为2时需要单独讨论。 
	if(n==2)
		return 1;
	//对2~n的数进行遍历，寻找因子。 
	for(i=2;i<n;i++)
	{
		if(n%i==0)
			return 0;
	}
	return 1;
}

int main()
{
	int n;
	cin>>n;
	if(judge1(n))
		cout<<n<<"是质数"<<endl;
	else
		cout<<n<<"不是质数"<<endl; 
	
	return 0;
}

这么做的思维简单，但相应的就会消耗大量时间，效率不高。

我们稍加改进

方法（二）：引入平方根

假设一个数n能被因式分解为两个数a和b，那么它们一定满足a<sqrt(n)<b。这个条件很容易理解。也就是说，找到比sqrt(n)小的因子就不需要再麻烦去算大的那个了。由此，我们可以减少一般的运算量。

#include <iostream>
#include <cmath>
using namespace std;
int judge2 (int n)
{
	int i;
	if(n==2)
		return 1;
    //这里只遍历至平方根
    //若是觉得取到sqrt(n)还不够保险，可以写成sqrt(n)+1,作用等同于（向上）取整函数。
	for(i=2;i<=sqrt(n);i++)
	{
		if(n%i==0)
			return 0;
	}
	return 1;
}
int main()
{
	int n;
	cin>>n;
	if(judge2(n))
		cout<<n<<"是质数"<<endl;
	else
		cout<<n<<"不是质数"<<endl; 
	cout<<sqrt(n);
	return 0;
}

二、思维拓展：筛选算法

方法（三）：埃氏筛

当我们找到一个质数时，这个质数的任意倍数（与另一数相乘）肯定都是合数，便把它筛除。从2开始遍历，先判断这个数是否被筛除过，如果没有，那么这个数肯定时质数，就用它来筛除它的倍数,否则就跳过。

#include <iostream>
//总的范围规定在这里 
const int maxn=1e6+7;
using namespace std;
//埃氏筛
int prime[maxn];
void initial()
{
	int i,j;
	//假设所有数字都是素数 
	for(i=0;i<=maxn;i++)
		prime[i]=true;
	//0和1不在谈论范围内
	prime[0]=prime[1]=false;
	//从2开始筛除 
	for(i=2;i<=maxn;i++)
	{
		if(prime[i])
		{
			for(j=2*i;j<=maxn;j+=i)	
			{
				prime[j]=false;
			}
		} 
	} 
		
} 
int main()
{
	//初始化后，相当于已经完成打表 
	initial();
	int n;
	cin>>n;
	if(mark[n])
		cout<<n<<"是质数"<<endl;
	else
		cout<<n<<"不是质数"<<endl;
	return 0; 
} 

这样的方法相比上面，已经很简便了。但是我们再思考一点：取一个数18，可以被分解为2*9或3*8，那么在筛除时将会访问两次。这样就导致了这种算法的时间复杂度为o(nlogn)。我们能不能通过一点调整，将方案再一次优化呢？

答案是肯定的！

方法（四）：欧拉筛/线性筛

为了解决这个问题，便出现了一个快速的线性筛法，也称为欧拉筛法。欧拉筛法没有冗余，不会重复筛除一个数，所以“几乎”是线性的，复杂度为O(n)。

欧拉筛法就是在埃氏筛的基础上，让每一个非质数都由其最小质因数筛去，从而避免了重复计算，提高了效率。

#include <iostream>
//总的范围规定在这里。 
const int maxn=1e6+7;
using namespace std;
//欧拉筛
int prime[maxn];
int mark[maxn];//标记数组，标记为1的不是质数；标记为0的是质数。 
void initial()
{
	int i,j,cnt=0;//cnt表示质数的个数。 
	memset(mark,0,sizeof(mark)); 
    mark[0]=mark[1]=1;
	for(i=2;i<=maxn;i++)
	{
		//若是i未标记，则得到一个质数为i。 
		if(mark[i]==0)
			prime[cnt++]=i;
		//标记目前得到的质数的i倍为非质数。 
		for(j=0;j<cnt&&prime[j]*i<maxn;j++)
		{
			//prime[j]*i<maxn和下面这句话同一个效果。 
			//if(i*prime[j]>=maxn)break; 
			//即若乘积超出最大范围，不做讨论，直接break。 
			mark[i*prime[j]]=true;
			//若该式成立，说明prime[j]是i的最小质因数，可以直接break。 
			if(i%prime[j]==0)
				break;
		}
	}
}
int main()
{
	//初始化后，相当于已经完成打表 
	initial();
	int n;
	cin>>n;
	if(!mark[n])
		cout<<n<<"是质数"<<endl;
	else
		cout<<n<<"不是质数"<<endl;
	return 0; 
} 

其中

if(i%prime[j]==0)
    break；

正是最关键的一步，因为这一步的存在，表明prime[j]是i的最小质因数，此时需要退出。这样便保证了接下来筛除的数也是被最小质因数筛掉的。

举个例子：

比如21=3*7，当枚举到质因数3（prime[j]==3)时，有21%3==0，此时应该退出。否则下一个质数为5，会筛去21*5=105。但是105=3*5*7，会优先被3筛去，不应被此时的5筛去。这样就会导致重复运算。

以上就是本期算法的全部内容，学会了赶紧去试一试吧！