A6313. 「JSOI2016」反质数序列
编程题
省选/NOI-
知识点
题目描述
对于一个长度为 $L\ge 2$ 的序列 $X:\{x_1,x_2,\cdots ,x_L\}$，如果满足对于任意 $1\le i\lt j\le L$，均有 $x_i+x_j$ 不为质数，则 JYY 认为序列 $X$ 是一个「反质数序列」。
JYY 有一个长度为 $N$ 的序列 $A:\{a_1,a_2,\cdots ,a_N\}$，他希望从中选出一个包含元素最多的**子序列**，使得这个子序列是一个反质数序列。
JYY 有一个长度为 $N$ 的序列 $A:\{a_1,a_2,\cdots ,a_N\}$，他希望从中选出一个包含元素最多的**子序列**，使得这个子序列是一个反质数序列。
输入格式
输入第一行包含一个正整数 $N$；
接下来一行包含 $N$ 个正整数，依次描述 $a_1,a_2,\cdots ,a_N$。
接下来一行包含 $N$ 个正整数，依次描述 $a_1,a_2,\cdots ,a_N$。
输出格式
输出一行一个整数，表示最长反质数子序列的长度。输入保证存在反质数子序列。
输入输出样例
输入 #1
6 1 2 2 3 4 10
输出 #1
4
说明/提示
对于 $10\%$ 的数据，满足 $N\le 10$；
对于 $40\%$ 的数据，满足 $N\le 150$；
对于 $80\%$ 的数据，满足 $N\le 1000$；
对于 $100\%$ 的数据，满足 $2\le N\le 3000,1\le a_i\le 10^5$。
对于 $40\%$ 的数据，满足 $N\le 150$；
对于 $80\%$ 的数据，满足 $N\le 1000$；
对于 $100\%$ 的数据，满足 $2\le N\le 3000,1\le a_i\le 10^5$。