I feel like there must exist a combinatoric proof of a theorem like: There is a prime between $n$ and $2n$, or $p$ and $p^2$ or anything similar to this stronger than there is a prime between $p$ and $(\prod_p p) + 1$ (Euclid's theorem).
I was trying to prove one by the Sieve on this grid
1 2 3 4 ... p p+1 p+2 p+3 p+4 ... 2p 2p+1 2p+2 2p+3 2p+4 ... 3p ........................... ........................... ........................... p^2 p^2+1 p^2+2 p^2+3 p^2+4 ...
but it did not work.
Do any good arguments like this exist? I don't expect anything as strong as Prime Number Theorem or even Bertrand, but surely a direct combination proof can prove that there are lots of primes?