找出所有不超过 N 的互质子集

Question

假设我有数字 1 到 N，我想根据以下标准将它们分成子集：

1. 每个数字只能出现在 1 个子集中。
2. 子集的元素必须互质。
3. 最小化子集总数。

我的方法是使用埃拉托色尼筛法找到最多 N 个素数，然后将它们相应地分成子集。例如，对于 N=5，我至少可以有两个子集 {1,2,3,5} 和 {4}。但我不确定如何在子集中分配元素，以便每个子集都具有互质元素。 这是我的逐步方法：

1. 第 1 组：{N 以内的所有素数}
2. 第 2 组：{2^k,3^k,5^k... p^k} 其中 p 是素数且 p^k < N。 对于不同的k值，我们可以形成不同的集合直到2^k< N.
3. 其余元素

问题是如何让第3步中的元素在子集中互质 有人可以就如何实现它以及我的逻辑中的缺陷提出更好的方法吗？

Answer 1

好像是一道题。没有两个偶数可以在同一个子集中，所以子集的最小数目是 floor(n/2)

如果n是偶数，你可以很容易地用子集{2i+1, 2i+2}实现边界。对于 n 奇数，您执行相同的操作，但将 {n-2, n-1, n} 放在最后一个子集中。请注意，相邻数字总是互质的，当 n 为奇数时，n,n-2 互质。