最大基數的無劃分子集

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的所有數字。

Answer 2

這與在具有多項式時間算法的comparability graph中查找獨立集合是一樣的，因爲它是完美的圖形。

看看這個：https://cs.stackexchange.com/questions/10274/how-to-find-the-maximum-independent-set-of-a-directed-graph