Solution:
Denote by $f(n)$ the least number of colors such that the integers $1,2, \ldots, n$ can be colored in the required way. We shall prove that $f(n) = \lfloor (k+1)/2 \rfloor$, where $2^{k-1} \leq n < 2^{k}$.

Observe that in the sequence $1, 2, 2^{2}, \ldots, 2^{k-1}$ we have no three numbers of the same color. This means that $f(n) \geq \lfloor (k+1)/2 \rfloor$.

Consider the following coloring by $\lfloor (k+1)/2 \rfloor$ colors (each color is identified with an integer among $1,2, \ldots, \lfloor (k+1)/2 \rfloor$). If $m = p_{1}^{\alpha_{1}} p_{2}^{\alpha_{2}} \ldots p_{t}^{\alpha_{t}} \leq n$, where $p_{i}$ are primes, then we have $h(m) := \alpha_{1} + \cdots + \alpha_{t} < k$ and we can correctly color $m$ by the color $\lfloor (h(m)+1)/2 \rfloor$.

If $a$ divides $b$ and $b$ divides $c$, then we have $h(a) < h(b) < h(c)$, i.e., $h(c) - h(a) \geq 2$. This means that the numbers $a$ and $c$ have different colors. Hence $f(n) = \lfloor (k+1)/2 \rfloor$.

Now applying the above formula for $n = 2004$ we get $f(2004) = 6$.