查找所有互素子集直至数量N

Question

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

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

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

1. 集合1：{所有素数最多为N}
2. 集合2：{2 ^k，3 ^k，5 ^k ... p ^k}}，其中p是素数，p ^k k
3. 其余元素

问题是如何使步骤3中的元素在子集中互质有人可以建议一种更好的方法来实现它以及我的逻辑缺陷吗？

Answer 1

似乎是一个技巧问题。同一子集中不能有两个偶数，因此子集的最小数目为floor（n / 2）

如果n为偶数，则可以轻松实现子集{2i + 1，2i + 2}的边界。对于n个奇数，执行相同的操作，但将{n-2，n-1，n}放在最后一个子集中。请注意，相邻数字始终是互质的，当n为奇数时，n，n-2是互质的。