## 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/2p), 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/2p3q), then the remaining primes are included within the set 6i - 1, 6i + 1. This is true because the entire set of integers can be represented as 6i, 6i + 1, 6i + 2, 6i + 3, 6i + 4, 6i + 5; all but 6i + 1, 6i + 5 are divisible by 2 and/or 3; and 6i + 1, 6i + 5 is equivalent to 6i - 1, 6i + 1. Therefore, only integers of the forms 6i - 1 and 6i + 1 need be checked.

Michael L. Hall