RE Greatest Factor Less Than Root
- From: "John W. Nicholson" <reddwarf2956@...>
>Let N be a integer. How does one go about finding the largest factor,If N is even, factor with 2 until you get N' odd.
>c, less than the square root of a number, N^(1/2)?
Once N' is odd, you can write N' as the difference of two squares:
N' = a^2 - b^2 =(a+b)(a-b)
Then, execute the following algorithm:
Start with a=ceil(Sqrt(N')).
Check if b= Sqrt(a^2-N') is an integer
if it is, END LOOP
if it isn't, then increase a, a=a+1
Largest factor of N' less than its square root = (a-b)
(Largest factor of N' bigger than its square root = (a+b) )
And so, you just have to remember the 2^r factor that we extracted earlier and calculate
your result properly for N=2^r·N'.
If you are interested in improving the algorithm, I recommend you look for some info about
"Fermat's factorization" and other methods like the "quadratic sieve"