按公因数计算最大组件大小

952. 按公因数计算最大组件大小 (Hard)

给定一个由不同正整数的组成的非空数组 A,考虑下面的图:

  • 有 A.length 个节点,按从 A[0] 到 A[A.length - 1] 标记;
  • 只有当 A[i]A[j] 共用一个大于 1 的公因数时,A[i] 和 A[j] 之间才有一条边。

返回图中最大连通组件的大小。

 

示例 1:

输入:[4,6,15,35]
输出:4

示例 2:

输入:[20,50,9,63]
输出:2

示例 3:

输入:[2,3,6,7,4,12,21,39]
输出:8

 

提示:

  1. 1 <= A.length <= 20000
  2. 1 <= A[i] <= 100000

相关话题

[并查集] [数学]


解法