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

エラトステネスの篩で解いた。