← 返回题目列表

Codeforces · 665/D

D. 简单子集

中文机器翻译题面 查看原题

如果对于所有正整数对 (i, j) (1 ≤ i < j ≤ k),xi + xj 是素数,则正整数元组 {x1, x2, ..., xk} 被称为简单元组。

给定一个数组 a,其中包含 n 个正整数 a1、a2、...、an(不必不同)。您想要找到数组 a 的一个具有最大大小的简单子集。

素数(或质数)是大于 1 的自然数,除了 1 和它本身之外没有正因数。

让我们将数组 a 的子集定义为一个元组,可以通过删除 a 中的一些(可能是全部)元素来从 a 中获得该元组。

输入

第一行包含整数 n (1 ≤ n ≤ 1000) — 数组 a 中整数的数量。

第二行包含 n 个整数 ai (1 ≤ ai ≤ 106) — 数组 a 的元素。

输出

在第一行打印整数 m — a 的简单子集的最大可能大小。

在第二行打印 m 个整数 bl — 具有最大大小的数组 a 的简单子集的元素。

如果有多个解决方案,您可以打印其中任何一个。您可以按任意顺序打印子集的元素。

示例

输入 #1

2
2 3

输出 #1

2
3 2

输入 #2

2
2 2

输出 #2

1
2

输入 #3

3
2 1 1

输出 #3

3
1 1 2

输入#4

2
83 14

输出#4

2
14 83