互质划分

$n\leq 10$ 的数据可以搜索来解决。

当 $n=1$ 时划分为一堆。当 $n>1$ 时把 $2i-1,2i$ 划分为一堆，若 $n$ 是奇数则把 $n$ 划入最后一堆。相邻的两个正整数互质，相邻的三个正整数 $2i-1,2i,2i+1$ 也是互质的，因为 $\gcd(2i-1,2i+1)=\gcd(2i-1,2)=1$，所以可以划分为 $\lfloor \frac{n}{2}\rfloor$ 堆，并且 $2$ 的倍数共有 $\lfloor \frac{n}{2}\rfloor$ 个，每两个都不能在同一组，于是是最少的堆数。