Slovenia — National Math Olympiad

Let $P$ be a polynomial satisfying the conditions of the problem and let $p$ be an arbitrary prime. Any prime $q$ dividing $P(p)$ also divides $p$, so $q = p$. Hence, for any prime $p$ we have $P(p) = \pm p^{m_p}$ for some non-negative integer $m_p$, which can depend on $p$.

The polynomials $P(x) = \pm 1$ obviously satisfy the conditions of the problem. Assume that the polynomial $P$ is not identically equal to $1$ or $-1$. Write
$$P(x) = a_n x^n + a_{n-1} x^{n-1} + \dots + a_1 x + a_0.$$
The polynomial $P$ can take the value $1$ and $-1$ only for a finite number of primes. So, there exist infinitely many primes such that
$$\pm p^{m_p} = P(p) = a_n p^n + a_{n-1} p^{n-1} + \dots + a_1 p + a_0$$
and consequently $p$ divides $a_0$. This is only possible if $a_0 = 0$. Write $P(x) = x^k Q(x)$ where $k \in \mathbb{N}$ and $Q$ is a polynomial with integer coefficients such that $Q(0) \neq 0$. Let $a$ be an integer and let $p$ be a prime dividing $Q(a)$. Then $p$ divides $P(a)$, so it also divides $a$. Hence, the polynomial $Q$ satisfies the conditions of the problem. Since $Q(0) \neq 0$, we conclude that $Q$ has to be identically equal to $1$ or to $-1$. The only possible polynomials are $P(x) = \pm x^n$, $n \in \mathbb{N}_0$ and all of these obviously satisfy the conditions of the problem.