给定一个包含 n 个正整数的集合 A，确定一个由尽可能少的元素组成的非空子集 B，使得它们的 GCD 为 1，并输出其大小。
例如：
5
6 10 12 15 18产生“3”的输出，而：
5
2 4 6 8 10等于“NONE”，因为无法确定子集。
所以它看起来很基本，但我仍然坚持下去。我对此的想法如下：我们知道集合中已经存在某个数字的倍数是没有用的，因为它们的除数是某个因子 k 的倍数，我们要寻找最小的子集。因此，对于每个 n i ，我们从进一步的计算中删除 k 是正整数的任何 kn i 。
不过，这就是我卡住的地方。接下来我该怎么办？如果已经有一些 2-element 子集，然后是 3-elem 等等，我只能想到一种愚蠢的蛮力尝试方法。我应该检查什么才能以更聪明的方式确定它？
这个问题绝对是一个很难解决的问题。我看不到任何计算效率高的算法可以保证在合理的时间内找到解决方案。
一种方法是：形成一个有序集合列表，其中包含原始集合中每个元素的主要因子。
现在您需要找到它们的交集为零的最小集合数。
为此，首先在列表中对这些集合进行排序，以便与其他集合的交集数量最少的集合朝向开始。现在什么是“最少的交叉点”？
这就是启发式方法发挥作用的地方。它可以是：
1. 设置与其他元素的交叉点数少于 MIN 数。
2. 设置与其他元素的交点数少于 MAX 数。
3.任何其他更合适的定义。
现在，您可能需要通过递归来昂贵地迭代所有组合以确定解决方案。
假设对于每个 A,B（两个元素），我们计算它们的最大公约数 D。然后我们将这些 D 值存储为以下形式的映射：A,B -> D 假设我们还存储反向映射 D ->甲，乙
如果至少有一个 D=1，那么我们就去 - 答案是 2。假设现在，不存在 D=1 的 D。答案为 3 需要满足什么条件？我认为这是一个：存在两个 D 值，例如 D1 和 D2，使得 GCD(D1, D2)=1。正确的？因此，现在我们已经将问题转换为所有 D 集合上的相同问题，而不是 As 和 Bs，并且我们已经将 2 答案的选项转换为 3 答案的选项。正确的？
我不是 100% 肯定只是大声思考。
但是这个转换后的问题更糟，因为我们必须存储更多的值。（N 个元素的组合第 2 类）。
不确定，你提出的这个问题对我来说似乎是一个难题。如果存在比蛮力更好的方法并且有兴趣知道它，我会感到惊讶。
您需要考虑（并寻找）的是：如果您知道它们的成对 GCD，是否有办法表达 GCD(a1, a2, ... aN)。如果有某种方法或公式，您可以稍微简化您的搜索（对于与所需标准匹配的最小子集）。
另请参阅此链接。也许它会有所帮助。
https://cs.stackexchange.com/questions/10249/finding-the-size-of-the-smallest-subset-with-gcd-1