最大 $\gcd$（maxgcd,1s/256M）

题目描述

给一个长度为 $n$ 的序列$a:a_1,a_2\cdots a_n$

定义序列的最大 $\gcd$ 为：每次选择两个正整数 $i,j(1 \leq i < j \leq n)$，最大的 $\gcd(a_i, a_j)$ 即为这个序列的最大 $\gcd$

！请使用文件输入输出！本题从maxgcd.in中读取输入，将答案输出到maxgcd.out中！直接从标准输入输出中读取/输出数据没有成绩！

输入描述

第一行两个整数 $n(2\leq n \leq 1\times10^6)$.

第二行 $n$ 个正整数 $a_1,a_2,a_3,\cdots ,a_n(1\leq a_i \leq 10^6)$，表示序列 $a$。

输出描述

一个整数，表示这个序列的最大 $\gcd$

输入样例1

3
1 2 2

输出样例1

2

样例解释

$\gcd(a_1, a_2) = \gcd(1,2) = 1$

$\gcd(a_1, a_3) = \gcd(1,2) = 2$

$\gcd(a_2, a_3) = \gcd(2,2) = 2$ 所以最大 $\gcd$ 为 $2$

数据范围

• 对于 $20\%$ 的数据，$2\leq n \leq 1\times10^3$, $1\ \le\ a_i \leq\ 10^6$
• 对于 $100\%$ 的数据，$2\leq n \leq 1\times10^6$, $1\ \le\ a_i \leq\ 10^6$