= Trial division
{title2=$p\leq\sqrt n$}
{wiki}
<Trial division> searches for <divisors> of an <integer> by testing candidate divisions. For <primality testing> of an <integer> $n>1$, testing the <prime numbers> up to $\sqrt n$ suffices: any <composite number> has a <prime factor> in that range. After finding a <prime factor>, repeated <division> removes its <prime power>, and testing the remaining quotient gives an elementary <integer factorization> method. This is useful for small inputs, but the number of candidates can grow rapidly with the input's digit count.
Back to article page
