title: How can we find maximum spanning tree in complete graph
body: <p>Given an array of <code>n</code> positive integers, how can we find maximum spanning tree in complete graph, considering weight of edge <code>(i, j) = gcd(a[i], a[j])</code>?</p>
  
  <p>I know one solution with complexity <code>O(n^2)</code>, but <code>n&lt;=10^5</code>, so I need something faster.</p>
  
  <p>UPD:</p>
  
  <p>As mentioned in comments: </p>
  
  <blockquote>
    <p>The question here is getting an algorithm that exploits the special
    structure of the graph.</p>
  </blockquote>