构建躲避球队

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'+1，沙发可以找到至少一个没有人打架的K‘队。)

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

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

Answer 1

我回答这个问题的方法是返回n+ 1中的质数。

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

1. 情况1: n中的所有质数和数字1 (trivial).
2. Case 2: n中的所有质数和n中的任意偶数(偶数可以被2整除，这消除了此选项)
3. 情况3:所有质数和奇数(任何合成的-non素数-奇数都可以被奇素数整除)。

关于数学证明，我对情况3不是100%确定，但似乎是这样的。

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