Trial division
Integer factorization algorithm / From Wikipedia, the free encyclopedia
Dear Wikiwand AI, let's keep it short by simply answering these key questions:
Can you list the top facts and stats about Trial division?
Summarize this article for a 10 year old
SHOW ALL QUESTIONS
This article is about the mathematical algorithm. For the judicial chamber of the International Criminal Court, see Judges of the International Criminal Court.
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.
![]() | This article includes a list of references, related reading, or external links, but its sources remain unclear because it lacks inline citations. (March 2014) |
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 × 5 × 7.
Trial division was first described by Fibonacci in his book Liber Abaci (1202).[1]