소수 부분 수열
시간 제한5초메모리 제한256 MB
길이가 2 이상인 연속 부분 수열 중 원소의 합이 소수인 가장 짧은 것을 찾고, 같은 길이라면 가장 앞에 있는 것을 출력한다.
문제
양의 정수로 이루어진 길이가 n인 수열이 있다. 소수 부분 수열이란 길이가 2 이상이고 원소들의 합이 소수(2 이상)가 되는 연속 부분 수열이다.
예를 들어 수열이 [3, 5, 6, 3, 8]이면, 길이가 2인 소수 부분 수열이 두 개(5 + 6 = 11, 3 + 8 = 11), 길이가 3인 소수 부분 수열이 한 개(6 + 3 + 8 = 17), 길이가 4인 소수 부분 수열이 한 개(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.를 출력한다.