Is there a result in the spirit of BertrandChebyshev which talks about the existence of prime powers between n and 2n (or 3n or something like that) for n large?
It follows from the prime number theorem that for fixed $k$, provided $n$ is sufficiently large, there is a prime $p$ such that $p^k$ is between $n$ and $2n$. Does this answer your question?

$\begingroup$ Thank you very much for your quick answer. Yes, it answers the question, and it goes to show the power of the PNT. $\endgroup$ – Chebolu Apr 27 '11 at 16:01

1$\begingroup$ I wonder if there is an elementary proof of this without using PNT, like Erdős' proof of Bertrand's Postulate? $\endgroup$ – Tony Huynh Apr 27 '11 at 17:24
Actually there is a power of 2. It goes to show the power of binary arithmetic ... : write 2n in binary and write zeroes after the initial one.

2$\begingroup$ In other words, if $2^{k  1}$ is the largest power of 2 less than n, then $n \leq 2^k < 2n$? $\endgroup$ – Ryan Reich Apr 27 '11 at 18:14

For fixed $k$, the existence of a prime power $p^k$ between $n$ and $2n$ is (asymptotically) equivalent to the existence of a prime $p$ between $m$ and $\sqrt[k]{2} m$ where $m = \sqrt[k]{n}$. Bachraoui gives an elementary proof here that there exists a prime between $m$ and $\frac{3}{2} m$ for sufficiently large $m$.
I remember reading on MO that it is known that similar elementary proofs exist for showing the existence of primes between $m$ and $(1 + \epsilon) m$ for any $\epsilon > 0$ and, furthermore, that the existence of these proofs itself depends on the PNT. However, I can't track down where I read this.

3$\begingroup$ Possibly it is this question you have in mind: mathoverflow.net/questions/53498/nontrivialcirculararguments $\endgroup$ – user9072 Apr 27 '11 at 19:00
