class UnionFind:
    def __init__(self):
        self.parent = self
        self.size = 1

    def get_root(self) -> "UnionFind":
        if self.parent is self:
            return self

        self.parent = self.parent.get_root()
        return self.parent

    def union(self, other: "UnionFind") -> None:
        root_large = self.get_root()
        root_small = other.get_root()
        if root_large is root_small:
            return

        if root_small.size > root_large.size:
            root_large, root_small = root_small, root_large

        root_small.parent = root_large
        root_large.size += root_small.size


class Solution:
    def largestComponentSize(self, nums: List[int]) -> int:
        N = max(nums)
        nums = set(nums)

        ufs = {n: UnionFind() for n in nums}
        prime_ufs = {}

        sieve = [True] * (N + 1)
        sieve[0] = sieve[1] = False
        for p in range(2, N + 1):
            if not sieve[p]:
                continue

            for n in range(p, N + 1, p):
                sieve[n] = False
                if n not in nums:
                    continue

                uf = ufs[n]
                if p not in prime_ufs:
                    prime_ufs[p] = uf
                else:
                    prime_ufs[p].union(uf)

        return max(
            uf.get_root().size for uf in ufs.values()
        )