At least one prime between $\sqrt{n}$ and $n$? Prove that for all $n>2$ there exists at least one prime $p$ such that $\sqrt{n}<p<n$ using elementary methods.
My try: If not, $\sum_{p<\sqrt{n}} (\lfloor n/p \rfloor-\lfloor \sqrt{n}/p \rfloor) \geq n-\sqrt{n}$  then...?
 A: Not a full answer, but hopefully helpful progress:
Look at  $M_p := \binom{p^2}{p~p~\ldots~p} = \frac{p^2!}{p!^p}$ where $p$ is a prime number,
let $v_q(x)$ the q-adic valuation of $M_p$ :
$$
v_q(M_p) = \sum_{k \geq 1} \lfloor\frac{p^2}{q^k}\rfloor - p\lfloor \frac{p}{q^k}\rfloor \leq (p-1)\lfloor \log_q(p^2) \rfloor
$$
Thus,
$$
 q^{v_q(M_p)} \leq p^{2(p-1)}
$$
In particular, if the interval $\{p+1,\ldots,p^2\}$ does not include any prime number, then
$$
M_p \leq p^{2(p-1)\pi(p)}
$$
where $\pi(p)$ is the number of prime numbers is the interval $\{p+1,\ldots,p^2\}$.
Moreover we know that $\ln(n!) \sim n \ln(n)$.Thus,
$$
\ln(M_p) \sim p^2 \ln(p)
$$
Because $2(p-1)\pi(p) \ln(p)$ is very small compared to $p^2 \ln(p)$
We know that your inequality will be true from a certain rank. Finding explicit bounds for a similar result to $\ ln (n!) \sim n \ ln (n)$, we will win...
Edit: 
$$n \ln(n) \geq \ln(n!) \geq \frac{2n}{3} \ln(\frac{n}{3})
$$
Then,
$$
\ln(M_p) \geq \frac{9p^2}{10} \ln(\frac{p^2}{10}) - p^2 \ln(p) = \frac{p^2}{10} (8\ln(p) - 9 \ln(10))
$$
Therefore, $\ln(M_p) \geq \frac{p^2}{2} \ln(p)$ since $ln(p) \geq 10^3$.
Yet, 
$$\pi(n) \leq 4 + \frac{1}{2} \frac{2}{3} \frac{4}{5} \frac{6}{7} (n+1) = 4 + \frac{8(n+1)}{35}$$
for all integer n$\geq 0$. 
Thus,
$$\frac{p^2}{2} \ln(p) \leq \ln(M_p) \leq \frac{2}{35}(p-1)(8p+140)\ln(p)$$
In the same way,
$$
35 p^2 \leq 4(p-1)(8p+140)
$$
ie
$$
0 \geq 35p^2-4(p-1)(8p+140) =3p^2-528p+560 > 3((p-88)^2-88^2)
$$
Therefore $p < 176$
Thus , it is known that the interval $ \{p+1,\ldots,p^2-1\}$ has a prime number when $p \geq 10^3$
but $3, 7, 47, 1009$ are prime numbers.
So the interval $\{p +1, \ldots , p ^ 2-1 \}$ has a prime number when $p \geq 2$ . This completes your exercise .
A: By way of a bump, I'm answering my question to give two facts and hope someone can give a good answer from this or at least convince me it will be too hard to do.
The first is that if $n=pq$ where $p$ and $q$ are primes then the claim is true. This is because if both $p,q<\sqrt{n}$ we get $n<n$.
The second is that the statement is equivalent to proving that if $p$ is a prime, the next prime $q$ is $q<p^2$. That is, the statement holds if it holds for $n=p^2$, $p$ prime. One does an induction argument, assuming there is a prime $p$ with $\sqrt{n}<p<n$, and then consider the interval $\sqrt{n+1}$ to $n+1$. If it doesn't contain a prime, it must be because $\sqrt{n}<p \leq \sqrt{n+1}$. Squaring gives the conclusion $n+1=p^2$, reducing the problem.
A: I think I'm close to a complete answer, using only elementary arguments.
Denote by $\pi(n)$ the number of primes leq $n$ and let $k=\pi(\sqrt n)$ be the number of primes $\leq\sqrt n$. Also, let $p_1<\ldots<p_k\leq \sqrt n$ be all such primes.
We want to show that $K=\pi(n)-\pi(\sqrt n)\geq 1$ for all $n$.
Counting non-primes by using the principle of inclusion and exclusion, one can show that
$$\pi(n)-\pi(\sqrt n)+1 =n-\sum_{1\leq i\leq k}[n/p_i] + \sum_{1\leq i<j\leq k}[n/p_ip_j]-\ldots+(-1)^k[n/p_1\cdots p_k].$$
Therefore, we want to show 
$$K=n-1-\sum_{1\leq i\leq k}[n/p_i] + \sum_{1\leq i_1<i_2\leq k}[{n\over p_{i_1}p_{i_2}}]-\ldots+(-1)^k[{n\over p_1\cdots p_k}]\geq 1.$$
Observe that $${n\over p_{i_1}\cdots p_{i_s}}
\geq [{n\over p_{i_1}\cdots p_{i_s}}]>{n\over p_{i_1}\cdots p_{i_s}}-1$$ and there are ${k\choose s}$ such terms in each sum. Replacing [] with the upper bound for odd $s$ and with the lower bound for even $s$ we get
\begin{align*}
K&=n-1-\sum_{1\leq i\leq k}[n/p_i] + \sum_{1\leq i_1<i_2\leq k}[{n\over p_{i_1}p_{i_2}}]-\ldots+(-1)^k[{n\over p_1\cdots p_k}]\\
&\geq n-\sum_{1\leq i\leq k}n/p_i + \sum_{1\leq i_1<i_2\leq k}{n\over p_{i_1}p_{i_2}}-\ldots+(-1)^k{n\over p_1\cdots p_k}-{k\choose 0}-{k\choose 2} -{k\choose 4}-\ldots\\
&=n\prod_{i=1}^k(1-1/p_i)-2^{k-1}.
\end{align*} 
Hopefully, induction can save us now to prove $K\geq 1$ for all $n$...
