#PQJ120x6220. QOJ 120_6220

    ID: 2572 传统题 1000ms 512MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:省选赛事:JSOI 2016数学动态规划数论

QOJ 120_6220

第二轮第二试 反质数序列 反质数序列 【故事背景】 由于发现太多以质数为条件的问题,计算机科学家JYY开始对质数厌烦了。 【问题描述】 对于一个长度为𝐿≥2的序列𝑋: 𝑥), 𝑥+, … , 𝑥<,如果满足对于任意1 ≤𝑖< 𝑗≤ 𝐿,均有𝑥" + 𝑥>不为质数,则JYY 认为序列X 是一个“反质数序列”。 JYY 有一个长度为N 的序列𝐴: 𝑎), 𝑎+, … , 𝑎-,他希望从中选出一个包含元素 最多的子序列,使得这个子序列是一个反质数序列。 【输入格式】 从文件prime.in 中读入数据。 输入第一行包含一个正整数N。 接下来一行包含N 个正整数,依次描述𝑎), 𝑎+, … , 𝑎-。 【输出格式】 输出到文件prime.out 中。 输出一行一个整数,表示最长反质数子序列的长度。输入保证存在反质数子 序列。 【样例输入】 6 1 2 2 3 4 10 【样例输出】 4 【数据规模与约定】 对于10%的数据满足𝑁≤10; 对于40%的数据满足𝑁≤150; 对于80%的数据满足𝑁≤1000; 对于100%的数据满足2 ≤𝑁≤3000, 1 ≤𝑎" ≤10A。