第一次讲课——筛选质数
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/
