## 题目

Given a non-empty array of unique positive integers A, consider the following graph:

• There are A.length nodes, labelled A[0] to A[A.length - 1];
• There is an edge between A[i] and A[j] if and only if A[i] and A[j] share a common factor greater than 1.

Return the size of the largest connected component in the graph.

Example 1:

Example 2:

Example 3:

Note:

• 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: $𝑂(𝑚𝑎𝑥(𝐴))$