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

Tamflexの貯蔵庫

やる気のない備忘録

aoj 0044

最小の素数と最大の素数 | Aizu Online Judge

全探索してからやったけど, 直近だけ探索すればよかったかも.

bool prime(int n)
{
  if(n<=1) return false;
  if(n==2) return true;
  if(n%2==0) return false;
  for(int i=3; i<=sqrt(n); i+=2)
    if(n%i==0) return false;
  return true;
}

void solve()
{
  vector<int> a;
  FOR(i,2,50100) if(prime(i)) a.push_back(i);
  int n;
  while(~scanf("%d",&n))
  {
    int l = *(lower_bound(a.begin(),a.end(),n)-1);
    int r = *(upper_bound(a.begin(),a.end(),n));
    printf("%d %d\n",l,r);
  }
}

int main()
{
  cin.tie(0);
  ios::sync_with_stdio(false);
  solve();
  return 0;
}