P5771 [JSOI2016] Anti-prime Sequence

For a sequence $X:\{x_1,x_2,...,x_L\}$ of length $L \ge 2$, if for any $1 \le i < j \le L$, $x_i + x_j$ is not a prime number, then JYY considers the sequence $X$ to be an “anti-prime sequence”. JYY has a sequence $A:\{a_1,a_2,...,a_N\}$ of length $N$. He wants to choose a **subsequence** with as many elements as possible such that this subsequence is an anti-prime sequence.

The first line contains a positive integer $N$. The next line contains $N$ positive integers, describing $a_1,a_2,...,a_N$ in order.

Output one integer in a single line, representing the length of the longest anti-prime subsequence. The input guarantees that an anti-prime subsequence exists.

For $10\%$ of the testdata, $N \le 10$. For $40\%$ of the testdata, $N \le 150$. For $80\%$ of the testdata, $N \le 1000$. For $100\%$ of the testdata, $2 \le N \le 3000$, $1 \le a_i \le 10^5$. Translated by ChatGPT 5