algorithm - 组建躲避球队

Question

一名教练正试图组建一支躲避球队。每个玩家都分配了一个学生 ID，如果一个玩家的 ID 除以另一个玩家的 ID，他们就会战斗。所以沙发想组队，这样队里就没人打架了。给定数字N(ID从1到N赋值)，找出最小的数字K沙发无法组成一个没有人战斗的团队。

input (N): 3 
output (K): 2 

例如，N = 3，

K = 3, {1,2,3} --> 玩家 1 和 2 打架了。

K = 2, {2,3} --> 没有人打架。

input (N): 4 
output (K): 2 

N = 4，

K = 4, {1,2,3,4} -> 多于一对玩家 (1,2), (1,3) 等进行战斗。

K = 3, {1,2,4}, {2,3,4}, {1,3,4} --> 玩家在所有队伍中战斗。

K = 2, {2,3} --> 没有人打架。

所以基本上，给定 N，找出沙发上不能让 K 名玩家任意组合的最小 K 值，这样就没人打架了。 (这也是一个榻榻米能找到至少K'队无人打架的最大K'+1。)

我和我的 friend 提出的一个贪婪的解决方案是尝试从给定的 N 中找到最大集合。最佳集合必须包含大数字，因为如果我们开始放入小数字，2、3、...，所有不能包括这些数字的乘数。因此，只要新数字不是集合中已包含的某个数字的约数，我们就可以开始将 N 到 N/2 放入集合中。我们不完全确定这个解决方案是否正确，所以我们很乐意讨论我们解决方案的正确性并听取其他人的想法。

我在一次在线编码测试中被要求解决这个编码问题，但不知道如何解决。

Answer 1

我的回答是返回 n + 1 中素数的个数。

k 是使不打架的对不可能存在的最小数字，例如，至少一对数能平分另一对，是吗？基于此，“最安全”的赌注是质数(因为它们不能彼此相除)。一旦你添加了非质数，你肯定会有一对“战斗”。

1. 情况 1:n 中的所有素数和数字 1(平凡的)。
2. 情况2:n中的所有质数和n中的任意偶数(偶数可以除以2，这就排除了这个选项)。

3. 情况 3:所有质数和一个奇数(任何复合-非质数-奇数都可以被一个奇质数整除)。

   我不是 100% 确定案例 3 关于数学证明，但似乎是这样。

免责声明:我还没有收到采访的反馈，这可能是完全错误的。