# Legendre's conjecture

If Legendre's conjecture is true, the gap between any two successive primes would be $O(\sqrt p)$. In fact the conjecture follows from Andrica's conjecture and from Oppermann's conjecture. Harald Cramér conjectured that the gap is always much smaller, $O(\log^2 p)$; if Cramér's conjecture is true, Legendre's conjecture would follow for all sufficiently large numbers. Cramér also proved that the Riemann hypothesis implies a weaker bound of $O(\sqrt p\log p)$ on the size of the largest prime gaps. Legendre's conjecture implies that at least one prime can be found in every revolution of the Ulam spiral.
Because the conjecture follows from Andrica's conjecture, it suffices to check that each prime gap starting at p is smaller than $2\sqrt p.$ A table of maximal prime gaps shows that the conjecture holds to 1018. A counterexample near 1018 would require a prime gap fifty million times the size of the average gap.