ACM is short for Algorithm, Coding, Math.

首先了解一下百度上对于质数的定义：

质数

质数（prime number）又称素数，有无限个。

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

换句话说，质数就是只能被1和它本身所整除。

根据这个定义，我们用C语言写成代码就是：

#include<stdio.h>
int main()
{
	int n,i;
	scanf("%d",&n);
	for(i=2;i<n;i++)
	{
		if(n%i==0)
		{
			printf("No\n");
			return 0;
		}
	}
	printf("Yes\n");
	return 0;
}

由于在ACM比赛时对程序的运行时间会做出限制，一般是1000ms也就是1秒内计算完毕。因此我们需要着重关注代码的运行效率和复杂度。复杂度分为空间复杂度和时间复杂度，空间复杂度就是程序运行时需要占用多大的内存，时间复杂度就是程序运行完成需要计算多少次。计算机大约每秒能够运算1亿次，因此我们要在有限的资源内对代码进行优化。

对于上面这个代码，n等于几，就需要进行几次运算，我们称它的时间复杂度为O(n);

我们可以看到，上面的代码中对于每个素数的判断，实际上有一大部分是多余的。比如前面已经计算过,一次10*1000，后面又要计算一次1000*10，因此我们只许计算到到i==100的时候就可以结束，因为10000=100*100，而再往后，计算步骤就与前面的重复了。

因此，上面的代码可以优化为：

#include<stdio.h>
int main()
{
	int n,i;
	scanf("%d",&n);
	for(i=2;i*i<=n;i++)
	{
		if(n%i==0)
		{
			printf("No\n");
			return 0;
		}
	}
	printf("Yes\n");
	return 0;
}

看，原本当n==10000时需要计算10000次的代码，在稍加修改后，只需要计算100次就可以得出答案了，这就是最简单的“算法”。这个代码的时间复杂度为O(sqrt(n));

然而在实际使用时，常常涉及多个质数同时计算，有时候甚至成千上万，如果每个质数都要计算一遍很容易就会超时。

比如这道题：

有n个整数a1~an (1<=n,ai<=10^6),请你判断输入的整数是不是质数，如果是请输出“Yes”,否则输出“No”。

时间限制：1000ms

由于数据量过大，使用前面的方法明显会超时，这时我们就需要学习一种新的算法：筛选质数，一次性把所有质数都求出来。

代码如下：

#include<stdio.h>

int a[1000000];

int main()
{
	int n,x,i,j;
	for(i=2;i<=1000000;i++)              //把数组里所有元素都初始化为1，表示这个数为质数，后续再进行筛选
		a[i]=1;
	for(i=2;i*i<=1000000;i++)            //从2开始，把每个数字的倍数都筛掉，因为质数除了1和它本身没有因数
	{
		for(j=i*2;j<=1000000;j+=i)
		{
			a[j]=0;
		}
	}
	scanf("%d",&n);
	for(i=0;i<n;i++)
	{
		scanf("%d",&x);
		if(a[x]==1)
			printf("Yes\n");
		else
			printf("No\n");
	}
	return 0;
}

运行结果：

其实上面的代码还可以进一步优化，因为如果一个数不是质数，那么这个数的倍数也一定不是质数。

因此，在代码中在加入一项条件判断：

#include<stdio.h>

int a[1000000];

int main() 
{
	int n,x,i,j;
	for(i=2;i<=1000000;i++)             
		a[i]=1;
	for(i=2;i*i<=1000000;i++)            
	{
		if(a[i]==1)                    //当a[i]不为质数的时候跳过筛选
		{
			for(j=i*2;j<=1000000;j+=i)
			{
				a[j]=0;
			}
		}
	}
	scanf("%d",&n);
	for(i=1; i<n; i++) 
	{
		scanf("%d",&x);
		if(a[x]==1)
			printf("Yes\n");
		else
			printf("No\n");
	}
	return 0;
}

代码的时间复杂度又降低了呢！

那么，还能不能再优化下去？

答案是，能！

在筛选函数内部的第二层循环这里：

for(j=i*2;j<=1000000;j+=i)
{
	a[j]=0;
}

当 j=i*k(k<i)时，实际上已经在之前被i==k的时候筛过一次了，因此，j的初始值其实可以直接从 i*i 开始。

最终代码为：

#include<stdio.h>

int a[1000000];

int main() 
{
	int n,x,i,j;
	for(i=2;i<=1000000;i++)              
		a[i]=1;
	for(i=2;i*i<=1000000;i++)            
	{
		if(a[i]==1)
		{
			for(j=i*i;j<=1000000;j+=i)
			{
				a[j]=0;
			}
		}
	}
	scanf("%d",&n);
	for(i=0;i<n;i++)
	{
		scanf("%d",&x);
		if(a[x]==1)
			printf("Yes\n");
		else
			printf("No\n");
	}
	return 0;
}

最后，我们再尝试一下对这个筛选质数的过程进行“封装”，当我们写别的代码想直接引用的时候可以直接搬运过来：

#include<stdio.h>
 
int isprime[1000000];                    
 
void prime()							  //
{
	for(int i=2;i<=1000000;i++)
		isprime[i]=1;
	for(int i=2;i*i<=1000000;i++)
	{
		if(isprime[i]==1)
		{
			for(int j=i*i;j<=1000000;j+=i)
			{
				isprime[j]=0;
			}
		}
	}
}                                        //需要引用的时候把这一部分复制过来，然后在主函数里面声明一下就可以啦
 
int main()
{
	int n,x,i,j;
	prime();
	scanf("%d",&x);
	for(i=0;i<n;i++)
	{
		scanf("%d",&x);
		if(isprime[x]==1)
			printf("Yes\n");
		else
			printf("No\n");
	}
	return 0;
}

文章的最后，来个习题练练手：NOI第n小的质数 http://noi.openjudge.cn/ch0105/44/

第一次讲课——筛选质数

质数

Thanks for Watch！