Thornhill Computer Club 2024 - February Mock CCC - Problem 4

During a party, people exchange gifts. Every person has written their favourite number on the gifts that they will give. If the sum of the numbers of the gifts exchanged between two people is prime, their exchange is considered a good exchange. Every person can give infinitely many gifts, but any pair of two people may only exchange their gifts once.

Given the number of people at the party and their favourite numbers, determine how many good exchanges are possible.

Input Specification

The first line will contain an integer ~N~ ~(1 \le N \le 2500)~.

The next line will consist of ~N~ space-separated integers, ~x_0, x_1, ... x_N~ representing the favourite numbers of each person ~(1 \le x_i \le 10^4)~.

Output Specification

On a single line, output the maximum possible amount of good exchanges that can happen at this party.

Sample Input 1

4
1 2 3 4

Sample Output 1

4

Explanation for Sample Output 1

The possible good exchanges are between the pairs (1,2), (1,4), (2,3), and (3,4). The sums of these pairs are 3, 5, 5, and 7, respectively, which are all prime. Hence, there are 4 possible good exchanges.

Sample Input 2

6
1 1 4 5 7 9

Sample Output 2

5

Explanation for Sample Output 2

The possible good exchanges are between the pairs (1,1), (1,4), (1,4), (4,7), and (4,9). The sums of these pairs are 1, 5, 5, 11, and 13, respectively, which are all prime. Hence, there are 5 possible good exchanges.

Note that (1,4) occurs twice, as there are two people whose favourite number is 1.