0044 - Prime Number II
#include <iostream> using namespace std; #define MAX 100000 bool is_prime[MAX+1]; void Sieve(void) { for (int i=0; i<=MAX; ++i) is_prime[i]=true; is_prime[0]=is_prime[1]=false; for (int i=2; i<=MAX; ++i) if ( is_prime[i] ) for (int j=i*2; j<=MAX; j+=i) is_prime[j]=false; } void Slove(int n) { for (int i=n-1; i>=2; --i) if ( is_prime[i] ) { cout << i << " "; break; } for (int i=n+1; i<=MAX; ++i) if ( is_prime[i] ) { cout << i << endl; break; } } int main(void) { int n; Sieve(); while (cin >> n) Slove(n); return 0; }
エラトステネスの篩で解いた。