def iter_primes(n: int) -> Iterator[int]:
    assert n >= 1
    if n % 2 == 0:
        yield 2
        while n % 2 == 0:
            n //= 2

    for factor in range(3, n + 1, 2):
        if factor > n or n == 1:
            break

        if n % factor != 0:
            continue

        yield factor
        while n % factor == 0:
            n //= factor


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:
        prime_factors = {}
        for n in nums:
            uf = UnionFind()
            for p in iter_primes(n):
                if p not in prime_factors:
                    prime_factors[p] = uf
                else:
                    prime_factors[p].union(uf)
        return max(
            uf.get_root().size for uf in prime_factors.values()
        )