# 分解质因数 + 并查集

每个数看作一个点，那么只有二者的 $gcd > 1$ 时，才会有边。

若直接每两个元素建图，那么时间复杂度为 $n^2$ 级别。

我们可以用质因数作为中间点，让元素与其所有的质因数构成边。最后检查连通分量的最大值即可

由于每个数最多有 $log\,n$ 个质因数，即最终的时间复杂度为 $O(n\,log(n\cdot A))$ ，其中 $A$ 为并查集的操作复杂度

	class Solution {
	public int largestComponentSize(int[] nums) {
	// 分解质因数 + 并查集
	// 以质因数作为转折点
	init(200002);
	int n = nums.length;
	for (int j = 0; j < n; j++) {
	int num = nums[j];
	// 分解质因数
	for (int i = 2; i * i <= num; i++) {
	boolean f = false;
	while (num % i == 0) {
	f = true;
	num /= i;
	}
	// 合并 j, i
	if (f) {
	union(j, n + i);
	}
	}
	// 若 num > 1，那么此时 num 也是一个质因数
	if (num > 1) {
	union(j, n + num);
	}
	}
	// 检查连通分量
	int ans = 0;
	int[] cnt = new int[n];
	for (int i = 0; i < n; i++) {
	ans = Math.max(ans, ++cnt[find(i)]);
	}
	return ans;
	}

	int[] father;

	public void init(int n) {
	father = new int[n];
	for (int i = 1; i < n; i++) {
	father[i] = i;
	}
	}

	public void union(int i, int j) {
	int lAncestor = find(i);
	int rAncestor = find(j);
	// 让质因数的父节点指向原数
	// 这样在分组的时候使得父节点不会超过 n
	// - cnt[find(i)]++;
	father[rAncestor] = lAncestor;
	}

	public int find(int x) {
	if (x == father[x]) {
	return x;
	}
	return father[x] = find(father[x]);
	}
	}

并查集 + 数学

困难并查集数学