题目分析

我们有一个长度为 $N$ 的序列 $A$，要从中选出一个子序列（不一定连续），使得这个子序列中任意两个不同元素的和都不是质数，并且要求这个子序列的长度最大。

关键观察

1. 质数的奇偶性
   除了 $2$ 以外，质数都是奇数。

   • 奇数 = 偶数 + 奇数
   • 偶数 = 偶数 + 偶数 或 奇数 + 奇数（但奇+奇=偶，但偶除了2以外都不是质数）
     所以质数由一个奇数和一个偶数相加得到（除了 $2$ 以外）。

2. 特殊情况：和为 2
   如果两个数都是 $1$，那么 $1+1=2$ 是质数，所以两个 $1$ 不能同时出现在子序列中。

3. 图论建模
   我们可以把这个问题看作：

   • 每个数字是一个节点。
   • 如果两个数字的和是质数，就在它们之间连一条边。
   • 我们要找一个最大独立集（没有边相连的点集）。
     但是最大独立集在一般图上是 NP 难的，不过这里图的结构特殊。

4. 二分图性质
   因为质数（除了 2）是奇数，所以它只能由偶数 + 奇数得到。
   所以我们可以把数字按奇偶性分成两部分：

   • 左边放偶数（除了 1 以外的奇数？注意 1 是奇数）
     实际上：
     • 偶数节点之间不可能有边（因为偶+偶=偶，不是质数除了 2，但 2 只能由 1+1 得到，所以偶+偶不可能为 2）。
     • 奇数节点之间：奇+奇=偶，偶质数只有 2，所以只有 1+1 会产生边。
       所以边只出现在：
     • 偶数和奇数之间（当偶+奇为质数时）
     • 奇数 1 和奇数 1 之间（1+1=2 是质数）

   因此这是一个二分图（偶数和奇数），除了 1 和自己有边。

5. 1 的特殊处理
   多个 1 不能同时选超过 1 个（因为 1+1=2 是质数）。
   所以我们可以先考虑：最多只能选一个 1。

算法思路

1. 把数字分成偶数集合 $E$ 和奇数集合 $O$。

2. 如果两个数 $e \in E$ 和 $o \in O$ 的和是质数，则它们不能同时选。

3. 问题转化为：在二分图中找最大独立集。
   二分图最大独立集 = 总点数 - 最小顶点覆盖
   根据 König 定理：二分图最小顶点覆盖 = 最大匹配

4. 所以：
   最大独立集 = 总点数 - 最大匹配

5. 但是要小心 1 的情况：

   • 如果选了多个 1，它们之间会冲突。
     解决方法：我们可以枚举是否选 1，然后对剩下的图求最大独立集。
     因为 1 最多一个，我们可以分别考虑：
     • 不选任何 1：在非 1 的偶数和奇数之间建图，求最大独立集。
     • 选一个 1：那么与这个 1 的和为质数的偶数不能选，把这些点删掉，再在剩下的图中求最大独立集，最后 +1（因为 1 被选了）。

6. 实现步骤：

   • 预处理质数表（到 $2\times 10^5$，因为 $a_i \le 10^5$，最大和 $\le 2\times 10^5$）。
   • 把输入数字分成偶数列表和奇数列表（注意 1 是奇数）。
   • 建二分图：偶数在左，奇数在右，如果偶+奇为质数则连边。
   • 用匈牙利算法求最大匹配。
   • 计算最大独立集。

算法步骤（最终）

1. 预处理质数判断（到 200000）。
2. 读入数据，分成偶数列表 E 和奇数列表 O。
3. 建图：E 和 O 之间，如果 e+o 是质数，则连边。
4. 用匈牙利算法求 E 与 O 之间的最大匹配 M。
5. 答案 = |E| + |O| - M。

注意：如果存在多个 1，则 O 中只保留一个 1 参与建图（因为多个 1 会冲突，我们只能选一个 1）。
所以我们可以：

• 如果 O 中有 k 个 1，我们只留一个 1 在 O 中，其余 1 不参与图（因为它们不能选）。
• 这样算出来的最大独立集就是答案。

复杂度

• 匈牙利算法：$O((|E|+|O|)\times M)$，这里 $|E|+|O| \le N=3000$，边数最多 $N^2/4$，可接受。