Question 9
Let $n$ be a positive integer. There are $n$ colors, with $n \ge 1$. Each integer from $1$ to $1000$ is to be painted one of the $n$ colors so that any two distinct numbers have different colors whenever one divides the other. Find the smallest $n$ for which this is possible.