CMO 2016 Problem 4

Let $n \geq 2$ be a positive integer and define $k$ to be the number of primes $\leq n$ . Let $A$ be a subset of $S = \{2,...,n\}$ such that $|A| \leq k$ and no two elements in $A$ divide each other. Show that one can find a set $B$ such that $|B| = k$ , $A \subseteq B \subseteq S$ and no two elements in $B$ divide each other.