题解：CF2167D Yet Another Array Problem

不难注意到，若想选择一个最小的数 $x(x>1)$，使得这一个数与集合 $\{a_i\}(a_i>1)$ 中的所有数字互质，那么 $x$ 一定是质数，所以我们枚举所有质数一一判断是否满足条件，我们可以转化为证明这个问题。

设 $A = \{a_1, a_2, \dots, a_n\}$ 是一个集合，其中每个 $a_i > 1$。

选择最小的 $x(x > 1)$，使得 $\gcd(x, a_i) = 1,\forall a_i \in A$ 证明这样的 $x$ 一定是质数。

我们考虑使用反证法。假设 $x$ 不是质数，则 $x$ 为合数。

由于 $x > 1$ 且为合数，$x$ 至少有一个质因数 $p(p > 1)$，满足 $p \mid x$ 且 $p \leq x/2 < x$。

由于 $x$ 与所有 $a_i$ 互质，即 $\gcd(x, a_i) = 1$ 对所有 $a_i$ 成立。

我们考虑质因数 $p$：

如果存在某个 $a_i$ 使得 $\gcd(p, a_i) > 1$，则由于 $p$ 是质数，有 $p \mid a_i$。

又因为 $p \mid x$，可得 $p \mid \gcd(x, a_i)$，从而 $\gcd(x, a_i) \geq p > 1$。 这与 $\gcd(x, a_i) = 1$ 矛盾。

因此，$p$ 必须与所有 $a_i$ 互质，即 $\gcd(p, a_i) = 1$ 对所有 $a_i$ 成立。

但 $p < x$ 且 $p > 1$，这与 $x$ 是满足条件的最小整数矛盾。

故假设不成立，$x$ 必为质数。

故所以我们枚举所有质数是正确的。