in reply to OT: Finding Factor Closest To Square Root
I'm not sure about "reasonably close", but I think that actually finding the factor closest to the square root is very difficult. Curiously, I think it is likely that even if one knew the factor closest to the square root, writing it as a product of the given prime factors is itself very difficult. (And the given problem seems harder than this latter one.)
This seems quite similar to the problem: given a finite set of natural numbers and another "target" natural number, find a subset of the given finite set whose sum is the target number? (or determine that this is not possible.) This is known to be NP hard (and so probably takes exponential time although this is a big open question.)
(Of course the problem may have no good solution - consider a number of the form 2p where p is a large prime.)
chas
This seems quite similar to the problem: given a finite set of natural numbers and another "target" natural number, find a subset of the given finite set whose sum is the target number? (or determine that this is not possible.) This is known to be NP hard (and so probably takes exponential time although this is a big open question.)
(Of course the problem may have no good solution - consider a number of the form 2p where p is a large prime.)
chas
In Section
Seekers of Perl Wisdom