This has got to be the world's oldest method. Nuff said.
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.
  1. Choose a number, N, you wish to factor.
  2. Choose another number, d.
  3. Use division algorithm to see if d is a divisor of N

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) )


Back to the factoring theory page
Back to the factoring page
Back to my home page
Back to the pslc home page

Paul Herman

Last Updated: May 13, 1998