<백준 알고리즘> 3896번: 소수 사이 순열

문제

연속한 소수 p와 p+n이 있을 때, 그 사이에 있는 n-1개의 합성수(소수나 1이 아닌 양의 정수)는 길이가 n인 소수 사이 수열라고 부른다.

양의 정수 k가 주어졌을 때, k를 포함하는 소수 사이 수열의 길이를 구하는 프로그램을 작성하시오. k를 포함하는 소수 사이 수열이 없을 때는 길이가 0이다.

예를 들어, 소수 23과 29의 소수 사이 수열은 {24, 25, 26, 27, 28}이고, 길이는 6이다.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 테스트 케이스는 한 줄로 이루어져 있고, 한 줄에 정수 k가 주어진다. 각각의 정수는 1보다 크고, 100000번째 소수(1299709)와 작거나 같다.

출력

각각의 테스트 케이스에 대해서 k가 합성수라면 k를 포함하는 소수 사이 수열의 길이를 출력한다. 그렇지 않으면 0을 출력한다.

예제 입력 1

5 10 11 27 2 492170

예제 출력 1

4 0 6 0 114

---

Solution

#include<stdio.h>
#include<stdbool.h>

bool isPrime(int N)
{
	if(N<2)
		return false;
	else if(N==2)
		return true;
	else if(N%2==0)
		return false;
	else
		for(int n=3;n*n<=N;n+=2)
			if(N%n==0)
				return false;
	return true;
}

int main(void)
{
	int T, small, big, k;

	scanf("%d", &T);

	for(int t=0;t<T;t++)
	{
		scanf("%d", &k);

		if(isPrime(k))
			printf("0\n");
		else
		{
			for(big=k+1;!isPrime(big);big++);
			for(small=k-1;small>0&&!isPrime(small);small--);

			printf("%d\n", small!=0?big-small:0);
		}
	}

	return 0;
}