Kolmogorov complexity of a sequence of prime numbers
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.