Notice: union each number with its prime factors, not with other numbers directly.
def largestComponentSize(nums):
uf = UnionFind(max(nums) + 1)
for num in nums:
for factor in range(2, int(sqrt(num)) + 1):
if num % factor == 0:
uf.union(num, factor)
uf.union(num, num // factor)
# Count component sizes
count = Counter(uf.find(num) for num in nums)
return max(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.