integer factorization subroutine

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

--
"Share what you know. Learn what you don't."
.

Relevant Pages