Legendre's conjecture, proposed by Adrien-Marie Legendre, states that there is a prime number between ${\displaystyle n^{2}}$ and ${\displaystyle (n+1)^{2}}$ for every positive integer ${\displaystyle n}$. The conjecture is one of Landau's problems (1912) on prime numbers; as of 2024^[update], the conjecture has neither been proved nor disproved.

If Legendre's conjecture is true, the gap between any prime p and the next largest prime would be ${\displaystyle O({\sqrt {p}}\,)}$, as expressed in big O notation.^{[lower-alpha 1]} It is one of a family of results and conjectures related to prime gaps, that is, to the spacing between prime numbers. Others include Bertrand's postulate, on the existence of a prime between ${\displaystyle n}$ and ${\displaystyle 2n}$, Oppermann's conjecture on the existence of primes between ${\displaystyle n^{2}}$, ${\displaystyle n(n+1)}$, and ${\displaystyle (n+1)^{2}}$, Andrica's conjecture and Brocard's conjecture on the existence of primes between squares of consecutive primes, and Cramér's conjecture that the gaps are always much smaller, of the order ${\displaystyle (\log p)^{2}}$. If Cramér's conjecture is true, Legendre's conjecture would follow for all sufficiently large n. Harald Cramér also proved that the Riemann hypothesis implies a weaker bound of ${\displaystyle O({\sqrt {p}}\log p)}$ on the size of the largest prime gaps.^[1]

By the prime number theorem, the expected number of primes between ${\displaystyle n^{2}}$ and ${\displaystyle (n+1)^{2}}$ is approximately ${\displaystyle n/\ln n}$, and it is additionally known that for almost all intervals of this form the actual number of primes (OEIS: A014085) is asymptotic to this expected number.^[2] Since this number is large for large ${\displaystyle n}$, this lends credence to Legendre's conjecture.^[3] It is known that the prime number theorem gives an accurate count of the primes within short intervals, either unconditionally^[4] or based on the Riemann hypothesis,^[5] but the lengths of the intervals for which this has been proven are longer than the intervals between consecutive squares, too long to prove Legendre's conjecture.

It follows from a result by Ingham that for all sufficiently large ${\displaystyle n}$, there is a prime between the consecutive cubes ${\displaystyle n^{3}}$ and ${\displaystyle (n+1)^{3}}$.^[6] Dudek proved that this holds for all ${\displaystyle n\geq e^{e^{33.3}}}$.^[7]

Dudek also proved that for ${\displaystyle m=5.10^{9}}$ and any positive integer ${\displaystyle n}$, there is a prime between ${\displaystyle n^{m}}$ and ${\displaystyle (n+1)^{m}}$. Mattner lowered this to ${\displaystyle m=1438989}$ ^[8] which was further reduced to ${\displaystyle m=155}$ by Cully-Hugill.^[9]

Baker, Harman, and Pintz proved that there is a prime in the interval ${\displaystyle [x-x^{21/40},\,x]}$ for all large ${\displaystyle x}$.^[10]

A table of maximal prime gaps shows that the conjecture holds to at least ${\displaystyle n^{2}=4\cdot 10^{18}}$, meaning ${\displaystyle n=2\cdot 10^{9}}$.^[11]