超时代码：
#include <iostream>
using namespace std;
//写一个函数判断是否是素数
bool isPrime(int num)
{int i=2;//cout<<"OK2";
for(;i*i<=num;i++){
if(num%i==0)break;
}
if(i*i>num)return true;
else return false;
}
int main()
{
int T;
cin>>T;
for(int j = 1;j <= T; j++){
int aim;
cin>>aim;
int count = 2;
if(isPrime(aim)){
cout<<0<<endl;
}
else{
for(int i = aim-1;;i--){if(isPrime(i))break;
else count++;}
for(int i = aim+1;;i++){if(isPrime(i))break;
else count++;}
cout<<count<<endl;
}
}
return 0;
}
超时原因是因为每次都单独去判断是否是素数，最后就在有大量素数时没法处理了
然后通过建立一个很大的bool型数组的方式将问题解决了
AC代码：
#include <iostream>
using namespace std;
bool * zhangjie=new bool [1299710];//首先是申请和分配空间的一个操作
int main()
{
for(int p=1;p<=1299710;p++){
zhangjie[p]=true;
}//这是进行初始化的一个操作
for(int i=2;i<1299710;i=i+1)
{
if(zhangjie[i]){
for(int j=i+i;j<=1299710;j=j+i)
zhangjie[j]=false;
}
}
int T;
cin>>T;
for(int j = 1;j <= T; j++){
int aim;
cin>>aim;
int count = 2;
if(zhangjie[aim]){
cout<<0<<endl;
}
else{
for(int i = aim-1;;i--){if(zhangjie[i])break;
else count++;}
for(int i = aim+1;;i++){if(zhangjie[i])break;
else count++;}
cout<<count<<endl;
}
}
return 0;
}
//今天讲课又有新的东西添加进来了
int prime[5500],tot;
bool isprime[50001];
void init()//先处理出50000以内的质数，可用来筛INT以内的质数
{ tot = 0;
memset(isprime, true, sizeof(isprime));
prime[tot++] = 2;
for(int i = 3; i < 50000; i += 2)
{ if(isprime[i])
{ prime[tot++] = i;
if(i * i < 50000)
{ for(int j = i + i; j < 50000; j += i)
isprime[j] = false; }
}
}
}
//就这个东西我们可以知道，整个过程中被命名为筛法求素数。
相对于以前的素数打表法，它的优点在于因为已经确定2是素数，除了2以外的其它偶数都是合数
所以优化后的结果就是每次的访问增量都为2
还有一个就是利用了
bool pd2(int x){ if(x==1)return false; for(int i=0;prime[i]*prime[i]<=x;i++) if(x%prime[i]==0)return false; return true;}我们现在只使用事先筛好的素数来验证一个较大数是否是素数。优化了多少？
100000以内的素数：9592个。和原版本相比较，大概优化了10倍的速度。