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 $\sqrt{{N}}$, since all integers greater than $\sqrt{{N}}$ have already had their cofactors tested.
• Recognize that if, for example, all factors of 2 are factored out of a number (to yield N^$\prime$ = N/2^p), then the problem has been reduced to finding the prime factorization of the smaller number N^$\prime$, using integers between 3 and $\sqrt{{N^{\prime}}}$.
• 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^{$\prime{^\prime}$} = N/$\left(\vphantom{ 2^p 3^q }\right.$2^p3^q$\left.\vphantom{ 2^p 3^q }\right)$), then the remaining primes are included within the set $\left\{\vphantom{ 6i-1, 6i+1 }\right.$6i - 1, 6i + 1$\left.\vphantom{ 6i-1, 6i+1 }\right\}$. This is true because the entire set of integers can be represented as $\left\{\vphantom{ 6i, 6i+1, 6i+2, 6i+3, 6i+4, 6i+5 }\right.$6i, 6i + 1, 6i + 2, 6i + 3, 6i + 4, 6i + 5$\left.\vphantom{ 6i, 6i+1, 6i+2, 6i+3, 6i+4, 6i+5 }\right\}$; all but $\left\{\vphantom{ 6i+1, 6i+5 }\right.$6i + 1, 6i + 5$\left.\vphantom{ 6i+1, 6i+5 }\right\}$ are divisible by 2 and/or 3; and $\left\{\vphantom{ 6i+1, 6i+5 }\right.$6i + 1, 6i + 5$\left.\vphantom{ 6i+1, 6i+5 }\right\}$ is equivalent to $\left\{\vphantom{ 6i-1, 6i+1 }\right.$6i - 1, 6i + 1$\left.\vphantom{ 6i-1, 6i+1 }\right\}$. Therefore, only integers of the forms 6i - 1 and 6i + 1 need be checked.