Largest Component Solution

Optimizations:

$1.$ Factor enumeration: only check up to $\sqrt{n}$ since factors come in pairs

$2.$ Sieve precomputation: precompute smallest prime factor for each number using Sieve of Eratosthenes, then factorize in $O(\log n)$

$3.$ 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())