# What Legendre's Conjecture Implies About the Upper Bound For the Prime Gap Above Any Natural Number

Big O of the square root of n, or big O of n to the power of one half, is what Legendre's conjecture implies about the upper bound for the prime gap above any natural number n, right?

I have seen it expressed as $O(\sqrt{p})$ but what does the p represent? I think p is used to represent any given prime. Can we use n to represent any given natural number and express it as $O(\sqrt{n})$ because the gap between any n and the next consecutive prime is bounded so, not only the gap between consecutive primes, assuming Legendre's conjecture?

• Let $n$ be any natural number $>1$ and let $p$ be the largest prime not exceeding $n$. Then $\sqrt{p} \le \sqrt{n}$, so if the gap from $p$ to the next prime is $O(\sqrt{p})$ then of course the gap from $n$ to the next prime (which is even smaller) is $O(\sqrt{n})$. – Erick Wong Sep 30 '14 at 15:50

Legendre's conjecture says that there is a prime between two consecutive (positive integer) squares. So between $n^2$ and $(n+2)^2$ there are two squares, so the gap between them is at most $(n+2)^2-n^2=4n+4$ (this can be improved). Let $p$ be the smaller one; then the larger one is at most $p+4n+4\le p+4\sqrt{p}+4$ and thus the gap is at most $4\sqrt{p}+4$.
The big-O notation just lets you ignore the details of what the constant is. $O(\sqrt p)$ means "bounded by a constant factor of $\sqrt p$".