Division of a free subset of maximum power

Question

A set S of natural numbers is called "free from division" if there are no separate elements x and y from S such that x is divisible by y. For example, S = {2, 3, 5} is division free, but {2, 3, 4, 5} is not, since 4 is divisible by 2. How would you calculate the maximum subset {1, 2, ..., n} which is division free? For example, when n = 10, then T = {4, 6, 7, 9, 10} is one of the maximal free subsets.

My nephew in elementary school asked me this seemingly simple mathematical problem. I can only think of brute force. But it gets ugly when n is great. Is there a decent algorithm for solving it by a computer?

Thanks.

Answer 1

Two numbers kand 2kcannot simultaneously belong to a subset without separation, so the subset cannot consist of numbers ceil(n/2).
Just take all the numbers from floor(n/2)+1to n.

Answer 2

This is the same as finding an independent set in the comparability diagram that has polynomial time algorithms, since it is an ideal graph.

Take a look: https://cs.stackexchange.com/questions/10274/how-to-find-the-maximum-independent-set-of-a-directed-graph