| 释义 |
Direct Search FactorizationDirect search factorization is the simplest Prime Factorization Algorithm. Itconsists 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 oftrial Divisors, but just including them is sometimes faster than the time required to exclude them. This approach is veryinefficient, and can be used only with fairly small numbers.
When using this method on a number  , only Divisors up to  (where  is theFloor Function) need to be tested. This is true since if all Integers less than this had beentried, then
 | (1) |
 of is  , then its Cofactor  (such that  ) must be Prime. To prove this, suppose that the smallest is . If  , thenthe smallest value  and  could assume is . But then
 | (2) |
 | (3) |
|