Prime Gap

문제 요약 : 어떤 수가 입력으로 들어옵니다. 이 수의 양옆에 있는 가장 가까운 소수 사이의 길이를 구하는 문제입니다. 입력된 수가 소수라면 0을 출력하면 됩니다. 

예를 들어, 4가 입력되면 4보다 작은 소수는 3이고, 4보다 큰 소수는 5입니다. 따라서 답은 2가 됩니다.

문제링크

해결 방법 : 에라토스테네스의 체를 이용해서 소수를 미리 구해두고, 문제를 풀면 정말 쉬운 문제입니다.

결과 : Accepted

소스코드

#include<iostream>
#include<cmath>

using namespace std;

const unsigned int MAX_NUM = 1299709;
unsigned int n;
unsigned int prime[MAX_NUM + 1];
unsigned int sqrtMaxNum = sqrt((double)MAX_NUM);

void makePrime() {
	//모두 1로 초기화
	for(int i = 1; i <= MAX_NUM; i++) {
		prime[i] = 1;
	}

	for(int i = 2; i <= sqrtMaxNum; i++) {
		if(prime[i] == 1) {
			for(int j = 2 * i; j <= MAX_NUM; j+= i) {
				prime[j] = 0;
			}
		}
	}
}

int main() {
	//freopen("input.txt", "r", stdin);
	makePrime();

	while(true) {
		cin >> n;
		if(n == 0) return 0;

		

		if(prime[n] == 1) cout << 0 << endl;
		else {
			int start = n-1;
			int end = n+1;
			while(true) {
				if(prime[start] == 1) break;
				start--;
			}
			while(true) {
				if(prime[end] == 1) break;
				end++;
			}

			cout << end - start << endl;
		}
	}

	return 0;
}