We claim that for every prime $p$, $f(p) = p^m$, where $m$ is a positive integer which (possibly) depends on $p$. Assume the claim for the time being. Since the degree $n$ of $f$ is positive, the claim forces $f(p) = p^n$ for sufficiently large primes $p$. Consequently, the polynomials $f$ and $X^n$ agree infinitely many times, so $f = X^n$.

Back to the claim, suppose that $f(p) = q^m$ for some distinct primes $p$ and $q$ and some positive integer $m$. Since $q^{m+1}$ divides the difference $f(p + kq^{m+1}) - f(p)$, $k = 1, 2, 3, \dots$, and $q^m$ divides $f(p)$ but $q^{m+1}$ does not, it follows that $q$ divides $f(p + kq^{m+1})$ but $q^{m+1}$ does not. Use Dirichlet's theorem to choose $k$ so large that $p+kq^{m+1}$ be prime and $f(p+kq^{m+1}) > q^m$. By hypothesis, $f(p+kq^{m+1})$ is a power of a prime. Recall that $q$ divides $f(p+kq^{m+1})$ to deduce that $f(p+kq^{m+1}) = q^r$ for some positive integer $r$. Finally, $f(p+kq^{m+1}) > q^m$ implies $r > m$, so $q^{m+1}$ divides $f(p+kq^{m+1})$ – a contradiction.