From: "John W. Nicholson" <

reddwarf2956@...>

>Let N be a integer. How does one go about finding the largest factor,

>c, less than the square root of a number, N^(1/2)?

If N is even, factor with 2 until you get N' odd.

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

DO

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

LOOP

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"

Regards!

Jose Brox