Kolmogorov complexity of a sequence of prime numbers

Let's say $p_1, p_2, p_3, \ldots $ is the increasing sorted sequence of all prime numbers. Prove that there exists a constant $n_0 \in \mathbb{N}$, so that for all $n \ge n_0$:
$$K(p_n) < \log_2(p_n) − 2.$$
Hint: Prime number theorem: $p_n \in \Theta (n \ln n)$.

I think, I could have a program A, which generates $p_n$ in $n\ln n$. I could just give A the index of my prime number and it would generate it.

Another idea of mine was to prove it by contradiction and assume the opposite is true but I can't really make that work.
My biggest problem is that I can't find an upper limit to the representation of prime numbers and start from there. Normally I'd just use the factorization for integers…

Any help is appreciated!

Since we can generate $p_n$ given $n$, $K(p_n) \leq K(n) + O(1) \leq \log_2 n + O(1)$. The prime number theorem implies that $p_n = \Theta(n\ln n)$, and so $\log_2(p_n) = \log_2 n + \log_2\log_2 n \pm O(1)$. You take it from here.

StackExchange Computer Science Q#69719, answer score: 3