Re: prime factorization
[Prev][Next][Index][Thread]
Re: prime factorization
Jonathan Todd Samuel writes:
> Note that if size is a concern, you can omit the while loop if you
> change the start value of B to 2, and change the increment of B
> from 2 to 1. I just liked the idea of skipping even numbers....
Ah, tradeoffs! The choice of an algorithm really does depend on
how (and how often) you are going to use the program -- that's why
there never can be a "once and for all" program.
In this case, if I were to be factoring many medium-sized integers,
I would want to use a pre-computed list of primes (including 2) to
choose my trial divisors from. But if I were to follow Jonathan's
approach I might also squeeze out any factors of 3 in the given
number, and then just test numbers of the form 6n - 1 and 6n + 1
as possible divisors. You could go further and squeeze out the 5's
and test numbers of the form 30n plus or minus 1, 7, 11 and 13,
but of course there comes a point of diminishing returns. It might
be interesting to set up a simulation to see how well the various
refinements of this idea perform on a given set of randomly-chosen
numbers. That is, if you had a clock built in...
RWW Taylor
National Technical Institute for the Deaf
Rochester Institute of Technology
Rochester NY 14623
>>>> The plural of mongoose begins with p. <<<<