How can we find maximum spanning tree in complete graph

Question

Given an array of n positive integers, how can we find maximum spanning tree in complete graph, considering weight of edge (i, j) = gcd(a[i], a[j])?

I know one solution with complexity O(n^2), but n<=10^5, so I need something faster.

UPD:

As mentioned in comments:

The question here is getting an algorithm that exploits the special structure of the graph.

Answer 1

Depending on the other constraints, you could use a variant of Kruskal's algorithm. For each input number, factor it and associate it with its divisors, e.g., given

[ 1,  2,  3,  4,  5,  8,  9, 10, 12]

we build a map

{ 1: [ 1,  2,  3,  4,  5,  8,  9, 10, 12],
  2: [ 2,  4,  8, 10, 12],
  3: [ 3,  9, 12],
  4: [ 4,  8, 12],
  5: [ 5, 10],
  6: [12],
  8: [ 8],
  9: [ 9],
 10: [10],
 12: [12]}.

Iterate over this map in key-descending order. For each list, unite those disjoint sets.