I am almost sure this does what you want. I am also convinced it is rather inefficient.

Yes on both counts. But I like the hand-crafted code approach :)

I rather hoped that someone would reveal a method using the prime factorization, or an efficient method for finding a factor reasonably close to the square root.