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

---

---

• Are you posting in the right place? Check out Where do I post X? to know for sure.
• Posts may use any of the Perl Monks Approved HTML tags. Currently these include the following:

  <code> <a> <b> <big> <blockquote> <br /> <dd> <dl> <dt> <em> <font> <h1> <h2> <h3> <h4> <h5> <h6> <hr /> <i> <li> <nbsp> <ol> <p> <small> <strike> <strong> <sub> <sup> <table> <td> <th> <tr> <tt> <u> <ul>

• Snippets of code should be wrapped in <code> tags not <pre> tags. In fact, <pre> tags should generally be avoided. If they must be used, extreme care should be taken to ensure that their contents do not have long lines (<70 chars), in order to prevent horizontal scrolling (and possible janitor intervention).
• Want more info? How to link or How to display code and escape characters are good places to start.