Direct search factorization is the simplest Prime Factorization Algorithm. It consists of searching for factors of a number by systematically performing Trial Divisions, usually using a sequence of increasing numbers. Multiples of small Primes are commonly excluded to reduce the number of trial Divisors, but just including them is sometimes faster than the time required to exclude them. This approach is very inefficient, and can be used only with fairly small numbers.
When using this method on a number , only Divisors up to
(where
is the
Floor Function) need to be tested. This is true since if all Integers less than this had been
tried, then
(1) |
(2) |
(3) |
See also Prime Factorization Algorithms, Trial Division