Informatica Online Judge

  소수 순열 [1190 / 04A6]

Time Limit(Test case) : 2000 (ms)
Number of users who solved : 13   Total Tried : 21


The Champion of this Problem (C++) : N/A
My Best Submission (C++) : N/A

[CCC 2005 Day1]

Background

n개의 자연수로 구성되어있는 순열이 주어졌을 때, 2개 이상 연속된 숫자들의 합이 2이상의 소수(prime)가 되는 경우를 소수화 된 순열이라고 정의하자.

예를 들어 아래와 같은 순열,

3 5 6 3 8

에는 길이가 2인 소수화 된 부분 순열은 2개(5+6=11, 3+8=11), 길이가 3인 소수화 된 부분 순열은 1개(6+3+8=17), 길이가 4인 소수화 된 부분 순열은 1개(3+5+6+3=17)가 있다.

Input

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

둘 째 줄부터 t줄에 걸쳐서, 첫 번째 값은 n(0 < n <= 10,000)이 입력되며, 공백이 하나 입력된 후, 다음 값부터 n개의 데이터가 공백으로 구분되어 입력된다.

단, 각 값은 10000 이하의 음이 아닌 정수이다.

Output

각각의 테스트케이스에 대해서, 소수화 된 부분 순열의 최소 길이를 출력하고, 다음 원소부터는 각 원소를 차례로 출력한다. 단, 같은 길이의 소수순열이 여러 개 있다면, 첫 번째로 발견되는 가장 짧은 부분 세트를 1개 출력한다.

만약, 소수화 된 부분 순열이 없는 경우 –1을 출력한다.

IO Example

입력
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

출력
2 5 6
3 4 5 4
-1

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]