首页 > 代码库 > 素数槽csuoj
素数槽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;
}