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!