站外水题求证明/伪/hack

给定 n 个正整数，将它们分组，使得每组中任意两个数互质，问最少分多少组？

这题很水，n

\le

10，别人说正解是暴搜，但我似乎摸到了一个贪心，类似拦截导弹：

记录当前答案的分组，枚举每一个元素，如果能直接加入某一个组，就直接加入，否则新建一个组

样例：

CPP

Input 1
6
14 20 33 117 143 175
Output 1
3

Input 2
10
1 2 3 4 5 6 7 8 9 10
Output 2
5

这两个样例贪心都能过，而且目前我找不到反例，也不会贪心性证明，求证明/伪/hack

讨论操作