划分最大基数的自由子集

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.