A7434. [GESP202606 五级]晚宴
编程题
普及-
知识点
题目描述
小明去参加晚宴。晚宴中有 $n$ 个菜肴，每个菜肴都有一个美味度，第 $i$ 个菜肴的美味度为 $v_i$。
晚宴规定小明只能**恰好**选取两道菜肴，并且这两道菜肴的美味度必须要互质（即最大公约数为 $1$）。
请帮助小明选取两道菜肴，使得两道菜肴美味度之和最大。
晚宴规定小明只能**恰好**选取两道菜肴，并且这两道菜肴的美味度必须要互质（即最大公约数为 $1$）。
请帮助小明选取两道菜肴，使得两道菜肴美味度之和最大。
输入格式
输入 $2$ 行，
第一行为一个正整数 $n$，表示菜肴的个数；
第二行为 $n$ 个整数 $v_1, v_2, \cdots, v_n$ 表示菜肴的美味度，整数之间以空格分隔。
第一行为一个正整数 $n$，表示菜肴的个数；
第二行为 $n$ 个整数 $v_1, v_2, \cdots, v_n$ 表示菜肴的美味度，整数之间以空格分隔。
输出格式
输出一个整数，表示两道互质菜肴美味度之和的最大值。
输入输出样例
输入 #1
5 3 5 7 35 105
输出 #1
38
说明/提示
### 样例解释 1
最优选择是 $3$ 和 $35$。
注意到，$105$ 与其他任意菜肴的最大公约数都大于 $1$，因此无法参与合法选择。
### 数据范围
$2 \le n \le 1000$, $1 \le v_i \le 1000000$。
数据保证不存在相同美味度的菜肴。
数据保证至少存在一种选取两道菜肴的方案。
最优选择是 $3$ 和 $35$。
注意到，$105$ 与其他任意菜肴的最大公约数都大于 $1$，因此无法参与合法选择。
### 数据范围
$2 \le n \le 1000$, $1 \le v_i \le 1000000$。
数据保证不存在相同美味度的菜肴。
数据保证至少存在一种选取两道菜肴的方案。