素数槽csuoj

超时代码：

#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;
}

素数槽csuoj,布布扣,bubuko.com

素数槽csuoj

原文：http://www.cnblogs.com/tianxia2s/p/3856143.html