Union by Prime Factors

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: $O(n \cdot \sqrt{M} \cdot \alpha(M))$ where $M$ is the maximum number.

Space: $O(M)$ for Union-Find array.