Trial division

Trial division is the most laborious but easiest to understand of the integer factorization algorithms. The essential idea is to test whether the integer to be factored can be divided evenly by each number in turn that is less than or equal to its square root. As an example, to find the prime factors of 70 one divides by successive primes: 70 divided by 2 gives 35, neither 2 nor 3 divides 35 evenly, and 35 divided by 5 gives 7, which is itself prime, so 70 equals 2 times 5 times 7. Trial division was first described by Fibonacci in his book Liber Abaci, written in 1202.