素因数分解利用するなら素因数分解そのものが手早くできてもダメでしょ？
それを何個か使って最も√nに近いもの探すのはかなり難しいんじゃなかったっけ？
つまり素因数分解n=Πpi^eiが与えられたとして、つぎは
0≦xi≦eiを動かすときΣxi log(pi) が1/2 log(n)に最も近くなるものを決定しなければならない
コレなんか名前ついてる問題で指数オーダーのアルゴリズムしか見つかってないんじゃなかったっけ？
素因子の数はlog(n)のオーダーで増えていくから、結局exp(c log(n)) のオーダーになって、cがどれくらいに収められるか、そもそも指数オーダー必要なのかも未解決なんじゃなかったっけ？