Any sufficiently large prime must be compressible, in the sense that $K(p)<\log_2{p}$ for any prime $p$ greater than some constant. It seems it is also implied that given any $d$, you can choose a lower bound for $p$ such that $\log_2 p-K(p)>d$, but I am not certain of this.
(See: Kolmogorov complexity of primes vs. composites in the limit?)
What I am struggling with now is why the same argument shouldn't apply to $np$, where $n$ is any integer and $p$ is again any prime over some (larger) constant.
For any naturals $a,b$, my understanding is that $K(ab) \leq K(a)+K(b)+C$ for some constant $C$ dependent on choice of language. If so, then allowing $b$ to be a large enough prime such that $K(b)-\log_2 b>C$, as given above, would ensure that $K(ab)<\log_2 K(ab)$. In other words, it would imply that any sufficiently large number which is incompressible in that sense would have an upper bound on the size of its prime factors.
Quite apart from the conceptual weirdness of all large incompressible numbers drawing from the same finite set of prime factors, that would also appear to conflict with the notion that almost all large integers are random/incompressible in this sense; yet, at as far as I know, greatest prime factors grow in a more-or-less predictable and regular way.
Since not all of these things can be so, I've gone awry on at least one of these points, but I can't figure out which. If someone can point me in the right direction, I'll consider this question resolved.
Well, I found at least one problem. As per Kolmogorov complexity of a product of two numbers, it looks like I was conflating prefix free Kolmogorov complexity, where $K(ab)=K(a)+K(b)+C$ would hold, with plain Kolmogorov complexity, which apparently permits only $K(ab)=K(a)+K(b)+C\log({a+b})$.
I would still welcome confirmation that this is the issue, so I'll leave this open for now.