Let $g(n)$ be the smallest prime factor of $f(n)$. (Since $f(n) \ge n$, $f(n)$ must have a prime factor unless $n=1$ and $f(1)=1$. In this case, we define $g(1)=1$.) First, we show that for any prime $p$ and any $k \ge 1$, $f(p^k)$ is a power of $g(p)$.

Suppose for the sake of contradiction that $f(p^k)$ is not a power of $g(p)$ for some $p$ and $k$. Choose $M$ sufficiently large so that $p^k < M \cdot 2013!$, and let $P$ be the set of primes less than or equal to $M \cdot 2013! + 1$. For any $q \in P$, we have
$$g(q) \le f(q) \le q + 2012 \le M \cdot 2013! + 2013,$$
and furthermore the numbers $M \cdot 2013! + i$ are composite for $2 \le i \le 2013$. It follows that $g(q) \in P$, and so $g$ can be treated as a function from $P$ to $P$. Clearly, $g$ is injective because $f(q_1)$ and $f(q_2)$ are relatively prime for any distinct $q_1, q_2 \in P$. Then, $g$ is bijective and in particular surjective.

Now we can apply the same reasoning we used on primes in $P$ to $p^k$. We have
$$f(p^k) \le p^k + 2012 \le M \cdot 2013! + 2013,$$
and so $f(p^k)$ has only prime factors in $P$. Suppose for the sake of contradiction that there is some prime $q \in P$ not equal to $g(p)$ which divides $f(p^k)$. Then, by the surjectivity of $g$, there exists $r \in P$ such that $g(r) = q$ (and with $r \neq p$). We then find that $p^k$ and $r$ are relatively prime, but $q$ divides both $f(r)$ and $f(p^k)$, contradicting the first condition in the problem. It follows that $f(p^k)$ is a power of $g(p)$, as claimed.

Next, we show that in fact $g(p) = p$. Indeed, suppose instead that $g(p) = q \neq p$. Then, choose $\ell$ sufficiently large so that $q^\ell > 2013$, and letting $P = p^{q^\ell - q^{\ell-1}}$, choose $k$ sufficiently large so that $P^k > q^\ell$. We find that
$$P^k \equiv 1^k \equiv 1 \bmod{q^\ell}.$$
By the second condition of the problem, the only possible residues of $f(P^k)$ modulo $q^\ell$ are the numbers between 1 and 2013, so in particular, $f(P^k)$ cannot be divisible by $q^\ell$. On the other hand, $f(P^k) \ge P^k > q^\ell$, so $f(P^k)$ cannot be any power of $q$, contradicting the fact that since $P^k$ is a power of $p$, $f(P^k)$ must be a power of $g(p) = q$. This proves our claim that $g(p) = p$.

Finally, let $p$ be any prime, and let $n$ be any positive integer relatively prime to $p$. Then, $f(p)$ and $f(n)$ are relatively prime, and since $f(p)$ is a power of $p$, it follows that $f(n)$ is not divisible by $p$. This is the contrapositive of the desired result, so we are done.

(By Gabriel Carroll) We first show that for any positive integer $N > 1$ and residue $r$, there exists a number $L$ such that $L \equiv r \bmod{N}$ and $f(L) = L$.

To see this, let $\{p_{i,j} \mid 1 \le i, j \le 2012\}$ be a set of distinct primes not dividing $N$ and larger than 2012. Also, let $\{q_i \mid 1 \le i \le 2012\}$ be another disjoint set of primes, also not dividing $N$ and larger than 2012.

By the Chinese Remainder Theorem, there exists a positive integer $K$ such that the following congruences hold:

* $K \equiv -i \bmod{p_{i,j}}$ for $1 \le i, j \le 2012$,
* $K \equiv 0 \bmod{q_i}$ for $1 \le i \le 2012$, and
* $K \equiv r + 1 \bmod{N}$.

Note that since $p_{i,j} > 2012$ and $1 \le i \le 2012$, it follows that $K$ is relatively prime to each $p_{i,j}$. Let $P$ be the product of the prime factors of $K$ not dividing $N$ and not equal to $q_i$ for some $i$.

By the Chinese Remainder Theorem again, there exists a positive integer $L$ such that the following congruences hold:

* $L \equiv -j \bmod{p_{i,j}}$ for $1 \le i, j \le 2012$,
* $L \equiv -i \bmod{q_i}$ for $1 \le i \le 2012$,
* $L \equiv r \bmod{N}$, and
* $L \equiv 1 \bmod{P}$.

We first claim that $K$ and $L$ are relatively prime. Indeed, suppose for the sake of contradiction that a prime $q$ divided both $K$ and $L$. By the construction of $L$, $q$ cannot be a factor of $P$ or any of the $q_i$. Thus, the only remaining possibility is that $q \mid N$. However, $K - L \equiv 1 \bmod{N}$, so this is impossible.

Thus, since $K$ and $L$ are relatively prime, we have by the first condition of the problem that $f(K)$ and $f(L)$ are relatively prime. Next, note that for any $1 \le i, j \le 2012$, we have
$$K + i \equiv L + j \equiv 0 \quad \text{mod } p_{i,j},$$
and for any $1 \le j \le 2012$, we have
$$K \equiv L + j \equiv 0 \quad \text{mod } q_j.$$
Recall from the second condition of the problem that $f(K)$ and $f(L)$ must take the forms $K + i$ and $L + j$, respectively, where $0 \le i, j \le 2012$. It follows from the above considerations that we must have $f(L) = L$, and by construction, we have $L \equiv r \pmod N$, as desired.

We can now quickly finish the problem. Suppose for the sake of contradiction that there is a prime $p$ and a number $n$ such that $p \mid f(n)$ but $p \nmid n$. Take $L$ to be a positive integer such that $L \equiv p \pmod{np}$ and $f(L) = L$. Then, $L$ is relatively prime to $n$, so $f(n)$ is relatively prime to $f(L)$. But $f(L) = L$ is divisible by $p$, a contradiction.