题目分析 对于一对数来说，如果他们含有共同的因子，且大于1，则不互质。 用一个map来记录出现过的因子，由于并不是所有的因子都需要被记录，比如一个数有因子 444，那么这个数也有 444 的因子 222，如 121212 有因子 1，2，3，4，6，121，2，3，4，6，121，2，3，4，6，12，存在因子 444 必然用时存在 444 的因子 222，存在因子 666，必然同时存在 666 的因子 333。 其中 4，6，124，6，124，6，12 不需要被记录，因为我们可以找到更小的因子 2,32,32,3，显然只需要记录所有的质因子即可。我们可以用埃氏筛先记录所有 ≤N\leq \sqrt{N}≤N 质数，再对每个数进行因子的统计。 这里可以分成两种情况。数ai≤Na_i \leq \sqrt{N}ai ≤N ，直接记录。数ai>Na_i \gt \sqrt{N}ai >N ，要除尽所有的质因子，剩下的数如果 >1\gt 1>1，则说明这个数存在一个 >N\gt \sqrt{N}>N 的质因子，也需要被记录。 最终如果质因子出现的次数大于 111，则说明出现了不互质的数。 AC代码 复杂度