Notice: union each number with its prime factors, not with other numbers directly.
function largestComponentSize(nums):
uf = new UnionFind(max(nums) + 1)
for each num in nums:
for factor from 2 to floor(sqrt(num)):
if num % factor == 0:
uf.union(num, factor)
uf.union(num, num / factor)
// Count component sizes
count = {}
for each num in nums:
root = uf.find(num)
count[root] = (count[root] or 0) + 1
return max of count.values
Each number unions with its factors. Numbers sharing a common factor end up in the same component.
Time: where is the maximum number.
Space: for Union-Find array.