문제
소수 p와 p+n사이 구간에 n-1 개의 연속된 합성수로 이뤄진 수열이 존재할 경우, p와 p+n 사이에는 길이 n의 prime gap이 존재한다고 한다.
예를 들어 소수 23, 29 사이에는 합성수인 24, 25, 26, 27, 28이 존재하므로 이는 길이 6의 prime gap이 존재한다.
임의의 정수 k에 대해서 k가 길이 몇의 prime gap에 속하는지 찾아내는 프로그램을 작성하라. 가령 k = 25일 경우 앞의 예시에서처럼 소수 23과 29사이에 숫자가 존재하므로 이 경우의 답은 6이다. 편의상 k를 포함하는 prime gap에 속하지 않을 경우에는 길이가 0인 prime gap에 속한다고 하자.
입력
입력의 첫 번째 줄에는 테스트 케이스의 개수 T(T≤1,000)가 입력된다.
그리고 그 다음 줄부터는 T개의 임의의 양의 정수 k가 한 줄에 하나씩 입력된다. 입력되는 숫자는 1이상, 100,000번째 소수인 1,299,709이하의 정수가 입력된다.
출력
입력된 k가 속한 prime gap의 길이를 순서대로 한 줄에 하나씩 출력한다.
예제
5
10
11
27
2
492170
4
0
6
0
114
출처
Asia Regional Contest 2007 in Tokyo B번
로그인해야 코드를 작성할 수 있어요.