BACKGROUND
This has got to be the world's oldest method. Nuff said.

BIG IDEA
This method looks for factors by *trying each prime out* one at a
time. A common technique is to start with 2, then try 3, 5, 7, ... etc.
It is easily provable that you only need to check up to sqrt(N) before
finding a factor. (NOTE: There may be prime factors larger than sqrt(N),
but that isn't important if you are just trying to find *a* factor.

METHOD
- Choose a number,
`N`, you wish to factor.
- Choose another number,
`d`.
- Use division algorithm to see if
`d` is a divisor of
`N`
- YES? - You found a factor! You are done.
- NO? - Go back to step 2

TECHNICAL ANALYSIS
Yes, that's all. This method is good for `N` < `5,000,000` or
so, but gets very slow, very quickly. Why? Because the theoretical
runtime grows `exponentialy` as the number of digits of `N`
increase. Exponential growth of an algorithm is a `bad thing`. In
fact, it is just about as bad as you can get. You really couldn't make an
algorithm (that works) any worse.
- Theoretical runtime:
- O( exp(# of digits in
`N`) )

LINKS

Back to the factoring theory page

Back to the factoring page

Back to my home page

Back to the pslc home page
Paul Herman

pherman@frenchfries.net

Last Updated: May 13, 1998