section_path: Computational methods/Trial division
section_name: Trial division
paragraph_text: Trial division
  
  The most basic method of checking the primality of a given integer n {\displaystyle n} is called trial division. This method divides n {\displaystyle n} by each integer from 2 up to the square root of n {\displaystyle n}. Any such integer dividing n {\displaystyle n} evenly establishes n {\displaystyle n} as composite; otherwise it is prime.Integers larger than the square root do not need to be checked because, whenever n = a ⋅ b {\displaystyle n=a\cdot b}, one of the two factors a {\displaystyle a} and b {\displaystyle b} is less than or equal to the square root of n {\displaystyle n}. Another optimization is to check only primes as factors in this range. For instance, to check whether 37 is prime, this method divides it by the primes in the range from 2 to 37 {\displaystyle {\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 grows exponentially as a function of the number of digits of these integers. 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.