Given a non-empty array of unique positive integers
A, consider the following graph:
- There are
A[A.length - 1];
- There is an edge between
A[j]if and only if
A[j]share a common factor greater than 1.
Return the size of the largest connected component in the graph.
1 <= A.length <= 20000
1 <= A[i] <= 100000
For each number, union itself with all its factors.
E.g. 6, union(6,2), union(6,3)
Time complexity: $𝑂(Σ𝑠𝑞𝑟𝑡(𝐴[𝑖]))$
Space complexity: $𝑂(𝑚𝑎𝑥(𝐴))$