Re: integer factorization subroutine

On 2007-03-19 08:02:11 -0300, Bart Vandewoestyne <MyFirstName.MyLastName@xxxxxxxxxx> said:

Hello all,

I would like to write a subroutine to factor an integer into it's
prime factors. I think the best interface to have is something
like the following:

subroutine factor(n, factors, multiplicities)
integer(kind=i4b), intent(in) :: n
integer(kind=i4b), dimension(:), intent(out) :: factors
integer(kind=i4b), dimension(:), intent(out) :: multiplicities

There are some little problems however:

1) I do not know in advance how many prime factors I will have for a certain n.
And since i want to keep my code F-compliant, I cannot use allocatable
dummy arguments. So I will probably also need a function nb_prime_factors(n)
that returns me the number of prime factors for a certain n. I can then
allocate the factor and multiplicity arrays with the correct size and pass
them to my factor subroutine. What do you guys think of this solution?

2) Seems like prime factoring is a whole science in itself. What i want for
now is a *readable* and *quite simple* method. I can (try to) optimize
the algorithm later. Has anybody done this in Fortran before? What
method/algorithm would be advisable?

The numbers n i want to be able to factor are say simply the integers
that are available for a standard 4 byte integer kind. So i don't really need
to be able to factor *superhuge* integers that are way over the limit
of the representable integers.

Any advice is welcome,
Bart

Anything beyond ultra trivial becomes rather technical.

To count the number of factors note that the worst case is all
factors are two. So estimate with base two logarithms. Since
you have a known max you can get away with a known fixed size
(until you change the max!).

If the number is composite then at least one of the factors will
be less or equal than the square root and at most one will be greater.
Integer square root is pretty simple or just take the square root
of HUGE(four bytes) which is a reasonalbe small number that will
not interfere with small demonstrations. Linear scan is trivially
easy and allows improvements of skipping multiples of 2, 3, 5, ...
with increasing complexity.

Be prepared to read lots of interesting mathematical history.



.

Relevant Pages