
ZOJ Problem Set  2203
Given a sequence of consecutive integers n,n+1,n+2,...,m, an antiprime sequence is a rearrangement of these integers so that each adjacent pair of integers sums to a composite (nonprime) number. For example, if n = 1 and m = 10, one such antiprime sequence is 1,3,5,4,2,6,9,7,8,10. This is also the lexicographically first such sequence. We can extend the definition by defining a degree dantiprime sequence as one where all consecutive subsequences of length 2,3,...,d sum to a composite number. The sequence above is a degree 2 antiprime sequence, but not a degree 3, since the subsequence 5, 4, 2 sums to 11. The lexicographically .rst degree 3 antiprime sequence for these numbers is 1,3,5,4,6,2,10,8,7,9. Input Input will consist of multiple input sets. Each set will consist of three integers, n, m, and d on a single line. The values of n, m and d will satisfy 1 <= n < m <= 1000, and 2 <= d <= 10. The line 0 0 0 will indicate end of input and should not be processed. Output For each input set, output a single line consisting of a commaseparated list of integers forming a degree dantiprime sequence (do not insert any spaces and do not split the output over multiple lines). In the case where more than one antiprime sequence exists, print the lexicographically first one (i.e., output the one with the lowest first value; in case of a tie, the lowest second value, etc.). In the case where no antiprime sequence exists, output No antiprime sequence exists. Sample Input
1 10 2 Sample Output
1,3,5,4,2,6,9,7,8,10 Source: East Central North America 2004 