Editing Prime number (section)

=== Number of primes below a given bound ===
{{Main|Prime number theorem|Prime-counting function}}
[[File:Prime-counting relative error.svg|thumb|upright=1.6|The [[Approximation error|relative error]] of <math>\tfrac{n}{\log n}</math> and the logarithmic integral <math>\operatorname{Li}(n)</math> as approximations to the [[prime-counting function]]. Both relative errors decrease to zero as {{tmath|n}} grows, but the convergence to zero is much more rapid for the logarithmic integral.]]
The [[prime-counting function]] <math>\pi(n)</math> is defined as the number of primes not greater than {{tmath|n}}.<ref>{{harvnb|Crandall|Pomerance|2005}}, [https://books.google.com/books?id=RbEz-_D7sAUC&pg=PA6 p.&nbsp;6].</ref> For example, {{tmath|1= \pi(11)=5 }}, since there are five primes less than or equal to&nbsp;11. Methods such as the [[Meissel–Lehmer algorithm]] can compute exact values of <math>\pi(n)</math> faster than it would be possible to list each prime up to {{tmath|n}}.<ref>{{harvnb|Crandall|Pomerance|2005}}, [https://books.google.com/books?id=ZXjHKPS1LEAC&pg=PA152 Section 3.7, Counting primes, pp. 152–162].</ref> The [[prime number theorem]] states that <math>\pi(n)</math> is asymptotic to {{tmath| n/\log n }}, which is denoted as
: <math>\pi(n) \sim \frac{n}{\log n},</math>
and means that the ratio of <math>\pi(n)</math> to the right-hand fraction [[convergent sequence|approaches]] 1 as {{tmath|n}} grows to infinity.<ref name="cranpom10">{{harvnb|Crandall|Pomerance|2005}}, [https://books.google.com/books?id=RbEz-_D7sAUC&pg=PA10 p.&nbsp;10].</ref> This implies that the likelihood that a randomly chosen number less than {{tmath|n}} is prime is (approximately) inversely proportional to the number of digits in&nbsp;{{tmath|n}}.<ref>{{cite book|title=The Number Mysteries: A Mathematical Odyssey through Everyday Life|first=Marcus|last=du Sautoy|author-link=Marcus du Sautoy|publisher=St. Martin's Press|year=2011|isbn=978-0-230-12028-0|pages=50–52|contribution=What are the odds that your telephone number is prime?|contribution-url=https://books.google.com/books?id=snaUbkIb8SEC&pg=PA50}}</ref>
It also implies that the {{tmath|n}}th prime number is proportional to <math>n\log n</math><ref>{{harvnb|Apostol|1976}}, Section 4.6, Theorem 4.7</ref>
and therefore that the average size of a prime gap is proportional to {{tmath| \log n }}.<ref name="riesel-gaps">{{harvnb|Riesel|1994}}, "[https://books.google.com/books?id=ITvaBwAAQBAJ&pg=PA78 Large gaps between consecutive primes]", pp. 78–79.</ref>
A more accurate estimate for <math>\pi(n)</math> is given by the [[offset logarithmic integral]]<ref name="cranpom10"/>
: <math>\pi(n)\sim \operatorname{Li}(n) = \int_2^n \frac{dt}{\log t}.</math>