読者です 読者をやめる 読者になる 読者になる

川のブログ

川の適当気ままなブログです。 

AOJ 0044 Prime Number II

こんにちは川です。

この問題は0009の応用?みたいな感じなので、0009の解説を見てから解いてください。

kawakawa.hatenablog.com

今回はまず素数表みたいなのをnの制約より少し大きめ(ここで大きすぎると時間内に終わらない)なのをつくり、その表を使って解いています。

 

ソースコード

 

#include<bits/stdc++.h>
using namespace std;
int main()
{
int num[50500],n,ma,anslow=0,anshigh=0;
ma=sqrt(50500);
for(int i=1;i<50500;i++)num[i]=0;
for(int i=2;i<ma;i++){
if(num[i]==0){
for(int j=2;j*i<50500;j++)num[j*i]=1;
}
}
while(cin>>n){
for(int i=1;anslow==0||anshigh==0;i++){
if(num[n-i]==0&&anslow==0)anslow=n-i;
if(num[n+i]==0&&anshigh==0)anshigh=n+i;
}
cout<<anslow<<" "<<anshigh<<endl;
anshigh=0;anslow=0;
}
}