algorithm - 整数数组的整除算法

Question

给定一个正整数数组 A。您需要创建数组 A 的一个子集，其中元素的最大数量具有属性，但是我们可以取该子集的任意两个数字(我们可以称之为 x 和 y ), 我们有 gcd(x,y) 大于 1。打印子集的元素。

例如，如果我们有 n = 4 并且数组是 {15, 7, 10, 6}，则输出需要是 {15, 10, 6}。

有没有比回溯更快的解决方案？

Answer 1

是的，我认为您有更好的解决方案。将其转化为图形问题:每个整数都是一个节点；两个节点 i 和 j 有一条边连接它们 iff gcd(i, j) > 1.

现在，您需要找到最大的全连接子图(也称为团)。一个小的研究将告诉你如何实现它。它效率不高，但更易于处理和可靠。