thu*_*zhf 7 math primes max combinatorics subset-sum
如何找到从2到1000的数字子集,在子集中任何两个数字不共享公共素数因子(例如,1000和500共享素因子2)的条件下,将给出最大总和？
上述问题的一个(可能更容易)变化:子集中最大的数字是多少？我们知道997是素数,并且很容易排除1000和998,因此问题变成子集中是否为999？
创建一个具有节点 {2, ..., 1000} 的图，并且当节点的 gcd > 1 时有边。该问题的解决方案与查找最大权重独立集问题相同，除了某些特殊情况外，该问题是 NP 困难的。这个图表案例看起来不像维基百科页面上的列表甚至这个列表中的空间案例。
更新
正如詹姆斯建议的那样，可以减少该图中的节点数量。假设数字 N 的质数分解签名p1^k1*...*pn^kn是一个元组(p1, ..., pn)。
第一个归约是当存在值较大且签名相同的节点时删除节点。这将图减少到 607 个节点。
下一步减少是删除N带有签名的节点(p1, ..., pn)，如果存在具有分解的签名的节点(p1, ..., pn)并且总和为>= N。这会将图减少到 277 个节点。
这些节点中有 73 个是孤立节点（素数 > 500。）