题目思路

模拟即可，首先通过并查集找到所有的连通块和大小，对最大的连通块做最小生成树，将最小的生成树权值输出即可。

代码

Java

题目内容

小红有一个$n$个整数的数组${a1,a2,...,a_n}$，他想两两将这些数字连成一张图，规则为:

从数组中选取任意两个数字$a_i$和$a_j(i≠j)$，如果$a_i+a_j$为质数，则将这两个点相连，边权即为$a_i+a_j$;

连出的图可能由若干个连通块构成，小红只关心那些点数最多的连通块，他想要知道，这些连通块能构成的全部生成树中，权值最小的那棵的权值是多少。

你只需输出这棵生成树的权值。

对于一张$n$个节点的图，选择其中$n-1$条边，使得所有顶点联通，这些边一定会组成一棵树，即为这张图的一棵生成树。可以证明，图中存在至少一棵生成树。

输入描述

第一行输入一个整数$n(1≤n≤10^3)$代表小红拥有的数字数量。

第二行输入$n$个整数$a_1,a_2,...,a_n(0≤a_i≤10^6)$代表小红的数字。

输出描述

在第一行上输出一个整数，代表在点数最多的连通块上，全部生成树中权值最小的那棵的权值。

示例1

输入

5
2 3 1 2 0

输出

10

说明

该样例连出的图如下图所示，由于仅有一个连通块，故直接输出权值最小的生成树即可。

示例2

输入

5
2 3 7 6 19

输出

5

说明

该样例连出的图如下图所示。