up previous next
find small prime factors of an integer
SmoothFactor(N: INT, MaxP: INT): RECORD |
This function finds the small prime factors of an integer. It simply
tries dividing by all primes up to the given bound
MaxP
.
The result is a list of the prime factors found together with the
unfactored part of N.
Be careful about supplying large values for
MaxP
(e.g. greater than
a million) as the function could take a very long time.
From version 5.0.4 the field are called
factors
and
multiplicities
instead of
Factors
and
Exponents
to comply with the naming conventions.
/**/ SmoothFactor(100,3);
record[factors := [2], multiplicities := [2], RemainingFactor := 25]
/**/ SmoothFactor(123456789,3700);
record[factors := [3, 3607], multiplicities := [2, 1], RemainingFactor := 3803]
|