Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I was wondering if someone could possibly help me verify the following:

For sufficiently large $n$ there is always a prime between $n- \sqrt{n}$ and $n$.

I am not sure if this is true or not. If it is true could you possibly explain me how the Prime number theorem is applied to get the answer?

share|improve this question

1 Answer 1

up vote 4 down vote accepted

I do not think you will have an easy time proving this result. There are a number of reasons for this. First, the Legendre conjecture states that there is at least one prime between $n^2$ and $(n+1)^2$, an interval of length that is order of $n$. As far as I know this is still unsolved. If we rescale your problem, we get that you want to show there are primes between $n^2-n$ and $n^2$ for $n$ large enough. Notice that $(n-1)^2=n^2-2n+1<n^2-n$. So if you could show your statement to be true, then you will have proven the Legendre conjecture for large enough $n$, and if you could produce a good lower bound on $n$ then a computer search will likely prove the Legendre conjecture.

The prime number theorem says $\pi(n)=O(n/\log(n))$. In fact the limit of the ratio is 1. So for all $0<C<1$, there exists a $N_c$, such that for all $n\geq N_c$,

$$c\leq \frac{\pi(n)}{n/\log(n)}$$

The interval you have is of length $\sqrt{n}$. In fact, the interval $[1,n]$ can be broken into $[1,n-\sqrt{n}]$ and $[n-\sqrt{n},n]$. In other words, you could try showing that there are at least $n-\sqrt{n}$ primes. No matter what $c$ you chose in the above, you will not attain a density this high for all large $n$.

You also might be interested in the Oppermann Conjecture which is a somewhat stronger version of your problem.

share|improve this answer
Now reread the question title: "Simple application ..." :) –  Hagen von Eitzen Nov 30 '12 at 23:43
You could try looking for asymptotic results of Legendre's conjecture. I'm not an expert but I don't think much is known. –  Alex R. Nov 30 '12 at 23:45
Ooopps. I guess it's not simple after all. Thank you very much! –  J Kasahara Nov 30 '12 at 23:56

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.