Editing Prime number (section)

=== Trial division ===
{{main|Trial division}}
The most basic method of checking the primality of a given integer {{tmath|n}} is called ''[[trial division]]''. This method divides {{tmath|n}} by each integer from 2 up to the [[square root]] of {{tmath|n}}. Any such integer dividing {{tmath|n}} evenly establishes {{tmath|n}} as composite; otherwise it is prime. Integers larger than the square root do not need to be checked because, whenever {{tmath|1= n = a\cdot b }}, one of the two factors {{tmath|a}} and {{tmath|b}} is less than or equal to the [[square root]] of {{tmath|n}}. Another optimization is to check only primes as factors in this range.<ref>{{cite book|title=Primes and Programming|first=Peter|last=Giblin|author-link=Peter Giblin|publisher=Cambridge University Press|year=1993|isbn=978-0-521-40988-9|page=[https://archive.org/details/primesprogrammin0000gibl/page/39 39]|url=https://archive.org/details/primesprogrammin0000gibl|url-access=registration}}</ref> For instance, to check whether 37 is prime, this method divides it by the primes in the range from 2 to {{tmath|\sqrt{37} }}, which are 2, 3, and 5. Each division produces a nonzero remainder, so 37 is indeed prime.

Although this method is simple to describe, it is impractical for testing the primality of large integers, because the number of tests that it performs [[exponential growth|grows exponentially]] as a function of the number of digits of these integers.<ref>{{harvnb|Giblin|1993}}, [https://archive.org/details/primesprogrammin0000gibl/page/54 p.&nbsp;54]</ref> However, trial division is still used, with a smaller limit than the square root on the divisor size, to quickly discover composite numbers with small factors, before using more complicated methods on the numbers that pass this filter.<ref name="p. 220">{{harvnb|Riesel|1994}}, [https://books.google.com/books?id=ITvaBwAAQBAJ&pg=PA220 p.&nbsp;220].</ref>