algorithm - 最大基数的无除法子集

Question

如果 S 中不存在不同的元素 x 和 y 使得 x 可以被 y 整除，则称正整数集 S 是“不可分割的”。例如，S = { 2, 3, 5 } 是无除法的，但 { 2, 3, 4, 5 } 不是，因为 4 可以被 2 整除。您将如何计算 { 1, 2, . .., n } 那是没有除法的？例如，当 n = 10 时，则 T = { 4, 6, 7, 9, 10 } 是最大自由分割子集之一。

小学的侄子问了我这道看似简单的数学题。我只能想到蛮力法。但是当 n 很大时它会变得很难看。有没有像样的算法可以用计算机解决？

谢谢。

Answer 1

k 和 2k 两个数不能同时属于无除子集，所以该子集不能包含超过 ceil(n/2) 数字。
简单地获取从 floor(n/2)+1 到 n 的所有数字。