整数数组可分性算法：求最大两两GCD>1子集及高效解法

当然有！回溯法虽然思路直观，但它枚举所有可能的子集，时间复杂度是O(2^n)，对于n稍大的数组（比如n>20）就完全不可用了。下面介绍一种高效且容易实现的贪心思路，时间复杂度可以降到O(k*n²)（k是出现最频繁的质数数量，通常很小），完全碾压回溯法。

核心思路 #

问题的关键在于：如果一个子集满足两两gcd>1，那么要么所有元素共享某个公共质数，要么任意两个元素都共享至少一个不同的质数（比如例子中的15、10、6，两两分别共享5、3、2）。我们可以通过质因数分解+贪心扩展的方式找到最优解：

具体步骤 #

1. 预处理：排除1
   1和任何数的gcd都是1，所以包含1的子集最多只能有1个元素（就是1本身）。先把数组中的1单独拎出来，最后再比较最优子集和1的大小。

2. 质因数分解与质数频率统计
   对数组中每个非1元素做质因数分解，统计每个质数对应的元素数量（即有多少个元素能被该质数整除）。比如例子中的数组：

   • 15 → {3,5}，3和5的计数各+1
   • 7 → {7}，7的计数+1
   • 10 → {2,5}，2和5的计数各+1
   • 6 → {2,3}，2和3的计数各+1
     最终得到各质数的计数：2→2，3→2，5→2，7→1。

3. 贪心扩展最优子集

   • 找到计数最大的质数集合（例子中是{2,3,5}，计数都是2）。
   • 对每个高频质数，先初始化子集为所有能被该质数整除的元素，然后遍历剩下的元素，检查它是否和子集中所有元素的gcd都>1，如果是就加入子集。
   • 保留所有尝试中得到的最大子集。

例子演示 #

对于数组{15,7,10,6}：

• 选质数2，初始子集是{10,6}。检查15：和10的gcd是5>1，和6的gcd是3>1，所以加入子集，得到{10,6,15}；7和10的gcd是1，无法加入。
• 选质数3或5，最终都会得到大小为3的子集，和上面的结果一致。
• 最终最大子集就是{15,10,6}。

为什么这个方法比回溯法快？ #

回溯法会暴力枚举所有2^n个子集，而这个方法只需要遍历有限个高频质数，每个质数对应的扩展过程是O(n²)，对于n=1000的数组，计算量也只有百万级别，完全在可接受范围内。

进阶优化（可选） #

如果想要进一步提升效率，可以用质因数掩码+动态规划的方法：把每个元素的质因数映射成二进制位，用DP记录每个质因数组合对应的最大子集大小。这种方法适合质因数数量较少的场景，时间复杂度可以降到O(n*2^k)（k是单个元素的质因数数量，通常不超过7）。

内容的提问来源于stack exchange，提问作者user9409795