# integer factorization subroutine

*From*: Bart Vandewoestyne <MyFirstName.MyLastName@xxxxxxxxxx>*Date*: Mon, 19 Mar 2007 11:02:11 GMT

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."

.

**Follow-Ups**:**Re: integer factorization subroutine***From:*Paul van Delst

**Re: integer factorization subroutine***From:*Gordon Sande

**Re: integer factorization subroutine***From:*Arjen Markus

- Prev by Date:
**Re: Append to screen IO** - Next by Date:
**Re: integer factorization subroutine** - Previous by thread:
**Print statement within If-Then block changes output!!!????** - Next by thread:
**Re: integer factorization subroutine** - Index(es):