# Trial division

Trial division is the simplest and easiest to understand of the integer factorization algorithms.

Given a composite integer n (throughout this article, n means "the integer to be factored"), trial division consists of trial-dividing n by every prime number less than or equal to [itex]\sqrt{n}[itex]. If a number is found which divides evenly into n, a factor of n has been found.

Trial division is guaranteed to find a factor of n, since it checks all possible prime factors of n. Thus, if the algorithm fails, it is proof that n is prime.

In the worst case, trial division is a very inefficient algorithm. If it starts from 2 and works up to the square root of n, the algorithm requires

[itex]\pi(\sqrt{n})[itex]

trial divisions, where [itex]\pi(x)[itex] is the number of primes less than x. This does not take into account the overhead of primality testing. If a variant is used without primality testing, but simply dividing by every odd number less than the square root of n, prime or not, it takes [itex]{\sqrt{n}\over 2}[itex] trial divisions. This means that for n with large prime factors of similar size (like those used in public key cryptography), trial division is computationally infeasible.

However, for n with at least one small factor, trial division can be a quick way to find that small factor. It is worthwhile to note that for random n, there is a 50% chance that 2 is a factor of n, and a 33% chance that 3 is a factor, and so on. It can be shown that 88% of all positive integers have a factor under 100, and that 91% have a factor under 1000.

For most significant factoring concerns, however, other algorithms are more efficient and therefore feasible.zh:试除法

• Art and Cultures
• Countries of the World (http://www.academickids.com/encyclopedia/index.php/Countries)
• Space and Astronomy