16.1.1 Prime_Factors Procedure

The Prime_Factors procedure uses an optimized direct search procedure
to calculate the prime factorization of a number *N*:

- Factors of
*N*are found by systematically performing trial divisions using a sequence of increasing numbers. - Note that a direct search to discover the prime factors does not need to go further than , since all integers greater than have already had their cofactors tested.
- Recognize that if, for example, all factors of 2 are factored out
of a number (to yield
*N*^{}=*N*/2^{p}), then the problem has been reduced to finding the prime factorization of the smaller number*N*^{}, using integers between 3 and . - Also, a procedure is used to eliminate multiples of small primes
from the testing procedure. Once the first two primes have been
factored out of the number (to yield
*N*^{}=*N*/2^{p}3^{q}), then the remaining primes are included within the set 6*i*- 1, 6*i*+ 1. This is true because the entire set of integers can be represented as 6*i*, 6*i*+ 1, 6*i*+ 2, 6*i*+ 3, 6*i*+ 4, 6*i*+ 5; all but 6*i*+ 1, 6*i*+ 5 are divisible by 2 and/or 3; and 6*i*+ 1, 6*i*+ 5 is equivalent to 6*i*- 1, 6*i*+ 1. Therefore, only integers of the forms 6*i*- 1 and 6*i*+ 1 need be checked.

Michael L. Hall