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 
. 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.
Trial division can be optimized in a few ways. For example, if the last digit of n is not 0 or 5, the algorithm can skip testing 5 as a factor. The same can be applied to 2 by checking the last digit, and 3 by checking the digit sum.
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
trial divisions, where pi(x) 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
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.