시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 128 MB 638 136 68 16.268%

문제

양의 정수로 이루어진 길이가 n인 수열이 있다. 소수 부분 수열이란 길이가 적어도 2이면서, 합이 2보다 크거나 같은 소수가 되는 연속 부분 수열이다.

예를 들어, 수열이 [3, 5, 6, 3, 8] 일 때, 길이가 2인 소수 부분 수열이 두 개(5 + 6 = 11, 3 + 8 = 11)이 있고, 길이가 3인 소수 부분 수열은 1개 (6 + 3 + 8 = 17), 길이가 4인 소수 부분 수열은 1개 (3 + 5 + 6 + 3 = 17) 가 있다.

수열이 주어졌을 때, 길이가 가장 짧은 소수 부분 수열을 구하는 프로그램을 작성하시오.

입력

입력의 첫째 줄에는 테스트 케이스의 개수 t (1 ≤ t ≤ 20) 가 주어진다.

각 테스트 케이스는 한 줄로 이루어져 있고, 줄의 첫 번째 정수 n은 (0 < n ≤ 10000) 수열의 길이이다. 다음에 주어지는 음이 아닌 정수 n개는 수열의 원소이다. 수열의 원소는 10000보다 작은 정수이다.

출력

각 테스트 케이스마다 가장 짧은 소수 부분 수열의 길이가 x라면 "Shortest primed subsequence is length x:"를 출력하고, 그 수열 공백으로 구분해 출력한다. 가장 짧은 소수 부분 수열이 여러가지면, 먼저 나오는 것을 출력한다.

소수 부분 수열이 없는 경우에는 "This sequence is anti-primed."를 출력한다.

예제 입력

3
5 3 5 6 3 8
5 6 4 5 4 12
21 15 17 16 32 28 22 26 30 34 29 31 20 24 18 33 35 25 27 23 19 21

예제 출력

Shortest primed subsequence is length 2: 5 6
Shortest primed subsequence is length 3: 4 5 4
This sequence is anti-primed.

힌트

출처

Olympiad > Canadian Computing Competition > CCC 2005 > Stage 2 4번