Trial division

Trial division is the most laborious but easiest to understand of the integer factorization algorithms. The essential idea behind trial division tests to see if an integer $n$ , the integer to be factored, can be divided by each number in turn that is less than the square root of $n$ .

For example, to find the prime factors of $n = 70$ , one can try to divide $70$ by successive primes: first, $70 / 2 = 35$ ; next, neither $2$ nor $3$ evenly divides $35$ ; finally, $35 / 5 = 7$ , and $7$ is itself prime. So $70 = 2 \times 5 \times 7$ .

Trial division was first described by Fibonacci in his book Liber Abaci (1202).^[1]

^ Mollin, Richard A. (2002). "A brief history of factoring and primality testing B. C. (before computers)". Mathematics Magazine. 75 (1): 18–29. doi:10.2307/3219180. JSTOR 3219180. MR 2107288.

[1] Mollin, Richard A. (2002). "A brief history of factoring and primality testing B. C. (before computers)". Mathematics Magazine. 75 (1): 18–29. doi:10.2307/3219180. JSTOR 3219180. MR 2107288.

[1]