$n\not\equiv 0\pmod{k}$, this means that $r_k(n)-r_k(n-1)=1$, where $r_k(n)$ is the remainder of $n$ when divided by $k$. Since $0$ is also $r_{n-1}(n-1)$, this means that there are exactly $n-2$ out of the $n-1$ numbers $k$ such that $n\not \equiv 0\pmod{k}$. In other words, there is exactly one integer $k$ less than $n$ such that $k|n$. But this equivalently means that $n$ is a prime number, since a number is prime iff it has exactly two divisors and thus exactly one proper divisor, which of course is $1$.

I found this solution.

We claim that all primes work. Note that if $d\nmid{n}, (n-1)\not\equiv d-1\pmod{d}$. Let $(n-1)\equiv r\pmod{d}$, then $n\equiv r+1\pmod{d}, r\neq{0}$. Therefore, $f(n)$ would increase by 1 for every $d\nmid{n}$ between 1 and $n-1$ exclusive. Let $d(n)$ be the number of divisors of $n$, so that out of the $n-3$ numbers that we consider dividing by $n-1$, excluding 1 since 1 will have a remainder of 0 when divided by any number, $d(n)-2$ of them will divide $n$. We exclude $n$ and 1 once again. Therefore, the function would supposedly increase by $n-3-(d(n)-2)$. However, we have to consider when $d\mid{n}$ from which $(n-1)\equiv d-1\pmod{d}$ and $n\equiv 0\pmod{d}$ so $f(n)$ would "loose" $d-1$ for each $d\mid{n}$. There would be $d(n)-2$ $d's$ here that would satisfy excluding $n$ and 1. Let $\sum{d_i}=d_1+d_2\cdots+d_{d(n)}$ where $d_1=1, d_{d(n)}=n$ and $d_1<d_2\cdots<d_{d(n)}$ where all $d_i$ are factors of $n$. After considering $d\mid{n}$, the function $f(n)$ will loose $\sum{d_i}-(n+1)-(d(n)-2)$. We must not forget $f(n)$ includes $n\pmod{n-1}$ which is 1. Therefore, the function will increase by $n-3-(d(n)-2)-\sum{d_i}+(n+1)+(d(n)-2)+1=2n-2-\sum{d_i}+1=n-2 \Longrightarrow \sum{d_i}=n+1$ which works for any prime.

I got the answer is right for all prime... @above, I believe substituting $p=5$ also works. Check my solution

Notice that we can rewrite $f(n)$ as adding $1$ to every remainder of $f(n - 1)$ from $1$ to $n - 1$, subtracting all divisors of $n$, and then adding $n$. This can be written as: $f(n) = f(n - 1) + n - 1 - d(n) + n = f(n - 1) - d(n) + 2n - 1$, where $d(n)$ is denoted as the sum of all divisors of $n$. Therefore we have $f(n - 1) - d(n) + 2n - 1 = f(n - 1) + n - 2$ which gives us $d(n) = n + 1$ which is true iff $n$ is prime.