Optimizations:
Factor enumeration: only check up to since factors come in pairs
Sieve precomputation: precompute smallest prime factor for each number using Sieve of Eratosthenes, then factorize in
Index mapping: if numbers are sparse, map to consecutive indices to save space
def largestComponentSize(nums):
uf = {}
def find(x):
uf.setdefault(x, x)
if uf[x] != x:
uf[x] = find(uf[x])
return uf[x]
def union(x, y):
uf[find(x)] = find(y)
for num in nums:
d = 2
while d * d <= num:
if num % d == 0:
union(num, d)
union(num, num // d)
d += 1
return max(Counter(find(n) for n in nums).values())