[정올 1901] 소수 구하기

http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1174&sca=99&sfl=wr_hit&stx=1901 

JUNGOL

#include <stdio.h>

int N;
int M[110];
bool bPrime[1000010];

void Input() {
	scanf("%d", &N);
	for (int i = 0; i < N; i++)
		scanf("%d", M + i);
}

bool IsPrime(int n) {
	if (bPrime[n]) return true;

	for (int i = 2; i * i <= n; i++) {
		if (n % i == 0) return false;
	}
	bPrime[n] = true;
	return true;
}

int GetUpperPrime(int n) {
	if (n > 1000000)		return 0;
	else if (IsPrime(n))	return n;
	else					return GetUpperPrime(n + 1);
}

int GetLowerPrime(int n) {
	if (n <= 0)				return 0;
	else if (IsPrime(n))	return n;
	else					return GetLowerPrime(n - 1);
}

int main(void) {
	Input();

	for (int i = 0; i < N; i++) {
		if (IsPrime(M[i])) {
			printf("%d\n", M[i]);
			continue;
		}

		int HighPrime = GetUpperPrime(M[i]+1);
		int HighGap = HighPrime - M[i];
		int LowPrime = GetLowerPrime(M[i]-1);
		int LowGap = M[i] - LowPrime;
		if (HighPrime == 0 || LowGap < HighGap) {
			printf("%d\n", LowPrime);
		}
		else if (LowPrime == 0 || HighGap < LowGap) {
			printf("%d\n", HighPrime);
		}
		else {
			printf("%d %d\n", LowPrime, HighPrime);
		}
	}

	return 0;
}