## 题目

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:

1 | Input: [4,6,15,35] |

Example 2:

1 | Input: [20,50,9,63] |

Example 3:

1 | Input: [2,3,6,7,4,12,21,39] |

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

## 代码

1 | class Solution: |