数据保证 $1 \leq n,a[i] \leq 1000$

正解：

贪心思路：

1.建图：每个数看做一个点，$O(n^2)$暴力枚举所有数对,每一数对$O(log n)$求gcd，若不唯一就连边，同时统计每个点的度；

2.贪心：按点的度数升序进行遍历，若该点仍存在，就$ans++$,并把所有和该点直接相连的点删去。直至所有点都已遍历或删去。

机房里有些人用贪心AC了，其余WA，30~90pts不等。

求严谨证明或反例（反例最好解释思路）