## Algorithm

Problem Name: 952. Largest Component Size by Common Factor

You are given an integer array of unique positive integers nums. Consider the following graph:

• There are nums.length nodes, labeled nums[0] to nums[nums.length - 1],
• There is an undirected edge between nums[i] and nums[j] if nums[i] and nums[j] share a common factor greater than 1.

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

Example 1:

Input: nums = [4,6,15,35]
Output: 4

Example 2:

Input: nums = [20,50,9,63]
Output: 2

Example 3:

Input: nums = [2,3,6,7,4,12,21,39]
Output: 8

Constraints:

• 1 <= nums.length <= 2 * 104
• 1 <= nums[i] <= 105
• All the values of nums are unique.

## Code Examples

### #1 Code Example with Javascript Programming

Code - Javascript Programming

const largestComponentSize = function (nums) {
const { sqrt } = Math
const n = nums.length
const uf = new UF(n)
const primes = {}
for (let i = 0; i  <  n; i++) {
const num = nums[i]
const prSet = primesSet(num)
for (const e of prSet) {
if (primes[e] == null) primes[e] = []
primes[e].push(i)
}
}

const vals = Object.values(primes)
for(const idxArr of vals) {
const len = idxArr.length
for(let i = 0; i  <  len - 1; i++) {
uf.union(idxArr[i], idxArr[i + 1])
}
}
let res = 0
const hash = {}
for(let i = 0; i  <  n; i++) {
const root = uf.find(i)
if(hash[root] == null) hash[root] = 0
hash[root]++
}
return Math.max(...Object.values(hash))

function primesSet(n) {
const limit = ~~(sqrt(n) + 1)
for (let i = 2; i < limit; i++) {
if (n % i === 0) {
const res = primesSet(n / i)
return res
}
}
return new Set([n])
}
}

class UF {
constructor(n) {
this.root = Array(n)
.fill(null)
.map((_, i> => i)
}
find(x) {
if (this.root[x] !== x) {
this.root[x] = this.find(this.root[x])
}
return this.root[x]
}
union(x, y) {
const xr = this.find(x)
const yr = this.find(y)
this.root[yr] = xr
}
}
Copy The Code &

Input

cmd
nums = [4,6,15,35]

Output

cmd
4

### #2 Code Example with Python Programming

Code - Python Programming

class Solution:
def largestComponentSize(self, A):
def find(i):
return i if i == parent[i] else find(parent[i])

def prime_factors(n):
res = set()
while n % 2 == 0:
n //= 2
for i in range(3, int(n**0.5) + 1, 2):
while n % i== 0:
n //= i
if n > 2:
return res
parent, dic = list(range(len(A))), {}
for i, n in enumerate(A):
for p in prime_factors(n):
if p in dic:
parent[find(i)] = find(dic[p])
dic[p] = i
for i, x in enumerate(parent):
parent[i] = find(x)
return max(collections.Counter(parent).values())
Copy The Code &

Input

cmd
nums = [4,6,15,35]

Output

cmd
4

### #3 Code Example with C# Programming

Code - C# Programming

using System;
using System.Collections.Generic;
using System.Linq;

namespace LeetCode
{
public class _0952_LargestComponentSizeByCommonFactor
{
public int LargestComponentSize(int[] A)
{
int maxValue = A.Max();
var uf = new UnionFind(maxValue + 1);

var numFactorMap = new Dictionary < int, int>();
foreach (int num in A)
{
var primeFactors = PrimeDecompose(num);

numFactorMap[num] = primeFactors[0];
for (int i = 0; i  <  primeFactors.Count - 1; ++i)
uf.Union(primeFactors[i], primeFactors[i + 1]);
}

// count the size of group one by one
int maxGroupSize = 0;
var groupCount = new Dictionary < int, int>();
foreach (int num in A)
{
var groupId = uf.Find(numFactorMap[num]);
groupCount.TryGetValue(groupId, out int count);
groupCount[groupId] = count + 1;

maxGroupSize = Math.Max(maxGroupSize, count + 1);
}

return maxGroupSize;
}

private IList < int> PrimeDecompose(int num)
{
var primeFactors = new List<int>();

int factor = 2;
while (num >= factor * factor)
{
if (num % factor == 0)
{
num /= factor;
}
else
factor += 1;
}

return primeFactors.Distinct().ToList();
}

public class UnionFind
{
private int[] parents;
private int[] ranks;

public UnionFind(int count)
{
parents = new int[count];
ranks = new int[count];

for (int i = 0; i  <  count; i++)
parents[i] = i;
}

public int Find(int index)
{
if (parents[index] != index)
parents[index] = Find(parents[index]);

return parents[index];
}

public void Union(int index1, int index2)
{
var pIndex1 = Find(index1);
var pIndex2 = Find(index2);

if (pIndex1 == pIndex2) return;
if (ranks[pIndex1] >= ranks[pIndex2])
{
parents[pIndex2] = pIndex1;
ranks[pIndex2]++;
}
else
{
parents[pIndex1] = pIndex2;
ranks[pIndex1]++;
}
}
}
}
}
Copy The Code &

Input

cmd
nums = [20,50,9,63]

Output

cmd
2