Given a set of numbers,find the pair which has the least LCM(Lowest Common Multiple)
<p>I used this approach.</p>

<ol>
<li>Found all possible <strong>nC2 pairs</strong> possible for n numbers.</li>
<li>Then individually found thier <strong>LCM</strong> by computing their <em>GCD and dividing the product of the two numbers by thier GCD.</em></li>
<li>Also maintained a variable which contained the least LCM value computed till then and finally output it.</li>
</ol>

<p>But this naive approach seems inefficient when the number values are very large (~10^9) since time complexity of GCD will depend on the magnitude of the number. Also it will be infeasible for very large values of N.
Is there any other better approach to this problem?</p>