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