in reply to
Re^2: OT: Finding Factor Closest To Square Root

in thread OT: Finding Factor Closest To Square Root

*
To fill a box of size log(N)/2, put the largest factor into the box. Then put the next largest factor that still fits in the box and insert it. Keep doing this until no more factors fit.
**
The above will get you the largest factor <= sqrt(N). To get the smallest factor >= sqrt(N), put all the factors in a box, and take them out again largest to smallest, until no more can be taken out. Finally, comapre the two answers to find the closest.
*

I don't think that does what you think. For example,

`2**3 * 19**3 = 54872,` and the square root is

`234.277...`.

Your method gives `19` as the largest less than the square root, and `2**3 * 19**2 = 2888` as the smallest greater than the square root. Notice that `19*2888 = 54872`.

A better result is `2**3 * 19 = 152` (because `19**2 = 361`).

-QM

--

Quantum Mechanics: The dreams stuff is made of