解题思路

设数组中一共有 $n$ 个质数，要求满足 $i \ne j$ 且 $a_i + a_j$ 为合数的有序二元组 $(i,j)$ 个数。

先考虑两个质数相加什么时候不是合数。

核心性质

• 若两个质数都大于 $2$，那么它们都是奇数

题目内容

在数论中，质数是大于 $1$且仅能被 $1$和自身整除的正整数；合数是大于$1$ 且除了 $1$和自身外还有其他正因子的正整数。

给定一个长度为$n$ 的数组 {$a_1,a_2,…,a_n$}，其中每个$a_i$都是质数。请你计算满足$a_i+a_j$为合数的有序二元组$(i,j)$的数量，其中 $i≠j$。

输入描述

第一行输入一个整数 $n (1≤n≤2×10^5)$，表示数组的长度；

第二行输入 $n$个整数 $a_1,a_2,…,a_n (1≤a_i≤2×10^5)$，表示数组 {$a_i$}，并保证每个 $a_i$ 都是质数。

输出描述

输出一个整数，表示满足$a_i十a_j$为合数的二元组($i,j$)的个数

样例1

输入

5
2 2 3 3 2

输出

8

说明

数组为 {$2,2,3,3,2$}。所有满足$i≠j$的有序二元组 ($i,j$) 共有 $5×4=20$ 个。其中满足 $a_i+a_j$ 为合数的二元组有：

• $a_i=2,a_j=2$：和为 $2+2=4$（合数）。由于数组中有 $3$个 $2$，可以组成$3×2=6$ 个这样的有序对。
• $a_i=3,a_j=3$：和为 $3+3=6$（合数）。由于数组中有$2$ 个$3$，可以组成 $2×1=2$个这样的有序对。

总计 $6+2=8$个。