Trial division ($p\le \sqrt{n}$)

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.