시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 19 10 9 50.000%

문제

n부터 m까지 숫자가 연속되어 있는 수열 n,n+1,n+2,...,m이 주어졌을 때, 이 수열의 수의 위치를 적절히 바꿔서 인접한 수의 합이 모두 소수가 아닌 수열을 소수 없는 수열이라고 한다. 예를 들어, n=1, m=10일 때, 1,3,5,4,2,6,9,7,8,10은 소수 없는 수열 중 하나이고, 그러한 수열 중 사전순으로 가장 앞서는 수열이다.

여기서 d차 소수 없는 수열은, 연속된 2,3,...,d개의 합이 모두 소수가 아닌 수열이다. 위에서 예로 든 수열은 2차 소수 없는 수열이다. 하지만, 5, 4, 2의 합이 11이 되고, 이 수는 소수이므로 3차 소수 없는 수열은 아니다. 3차 소수 없는 수열 중 사전순으로 가장 앞서는 것은 1,3,5,4,6,2,10,8,7,9이다.

n, m, d가 주어졌을 때, 사전순으로 가장 앞서는 d차 소수 없는 수열을 구하는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, n, m, d가 공백으로 구분되어져 있다. n, m, d는 1 ≤ n < m ≤ 1000, 2 ≤ d ≤ 10을 만족한다. 입력의 마지막 줄에는 0 0 0이 주어진다.

출력

각 테스트 케이스에 대해서, d차 소수 없는 수열을 콤마(,)로 구분해서 출력한다. 만약 그러한 수열이 여러개일 경우에는 사전순으로 가장 앞서는 것을 출력한다. (즉, 첫째 수가 가장 작은 수열, 같을 때는 두번째 수가 작은 수열, ....) 만약, d차 소수 없는 수열이 없는 경우에는 "No anti-prime sequence exists."을 출력한다.

예제 입력

1 10 2
1 10 3
1 10 5
40 60 7
0 0 0

예제 출력

1,3,5,4,2,6,9,7,8,10
1,3,5,4,6,2,10,8,7,9
No anti-prime sequence exists.
40,41,43,42,44,46,45,47,48,50,55,53,52,60,56,49,51,59,58,57,54

힌트