[0952] 按公因数计算最大组件大小

• GitHub
• http://leetcode.xuezhisd.top/post/817a80.html
• https://leetcode.com/problems/largest-component-size-by-common-factor
• https://leetcode-cn.com/problems/largest-component-size-by-common-factor

题目描述

给定一个由不同正整数的组成的非空数组 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

Related Topics

并查集

数学

题目解析

• [请一句话描述题目…]

不确定性

方法一：[算法名称]

分析

思路

注意

知识点

复杂度

代码

//

方法二：[算法名称]

分析

思路

注意

知识点

复杂度

代码

//

相关题目