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