For example for n=2 coloring odd numbers red, numbers of the form 4k+2 blue and so on works.

This problem was posed in the KoMaL for n+1 prime, by Peter Pach Pal. I verified it for all n<30, I think with a computerprogram one can easily verify it for much bigger numbers by trying certain periodic colorings.

Ideas. As there is a lot of discussion going on, I thought I share here my attempts as Ewan and Gowers took similar paths. First of all, if we denote the primes by $p_i$ and the largest prime not bigger than $n$ by $p_d$, then it is sufficient to color the numbers of the form $\Pi p_i^{\alpha_i}$. This is equivalent to coloring $\mathbb Z^d$ with n colors such that the translates of a special poliomino are all rainbow colored, meaning they contain all $n$ colors. This is also equivalent to tiling the space with translates of this poliomino. The easiest way to give a coloring is if we have some nice periodicity, eg. if n+1 is prime, then $\Pi p_i^{\alpha_i} \mod (n+1)$ is such, whenever we go in a direction, it corresponds to an authomorphism of $Z_{n+1}^*$. Another possibility is to give a "linear" coloring using the addition $\mod n$, for example for $n=5$, one can take $x+3y+4z \mod 5$. So far I could always find such a linear coloring but I cannot prove that it always exist, eg. we have too many constraints to use the combinatorial nullstellensatz.