from collections import Counter

class UnionFind:
    def __init__(self, _arrSize):
        self.arr = [i for i in range(_arrSize)]

    def find(self, i):
        # skip "a" looking for "a"
        if self.arr[i] != i:
            self.arr[i] = self.find(self.arr[i])
        return self.arr[i]

    def union(self, a, b):
        # a and b need to be union'ed
        a_root = self.find(a)
        b_root = self.find(b)
        # set a as the root
        self.arr[a_root] = b_root

class Solution:
    def largestComponentSize(self, A: List[int]) -> int:
        fullFactors = []
        for num in A:
            factors = []
            tempFactor = 2
            while tempFactor * tempFactor <= num:
                if num % tempFactor == 0:
                    while num % tempFactor == 0:
                        num /= tempFactor
                    factors.append(tempFactor)
                tempFactor += 1
            if num > 1 or not factors:
                factors.append(num)
            fullFactors.append(factors)

        # Input: [20,50,100,9,63,21,49]
        # fullFactors: [[2, 5.0], [2, 5], [2, 5], [3], [3, 7.0], [3, 7.0], [7]]
        # primes are guaranteed to be sorted
        primes = list({p for factors in fullFactors for p in factors})
        # map each prime to its index
        prime_to_index = {p: i for i, p in enumerate(primes)} # {2: 0, 3: 1, 5.0: 2, 7.0: 3}

        unionFind = UnionFind(len(primes))

        for factors in fullFactors:
            for f in factors:
                unionFind.union(prime_to_index[factors[0]], prime_to_index[f])
        # Counter will count how many times each value in an array appears.
        freqMap = [ unionFind.find(prime_to_index[factors[0]]) for factors in fullFactors ] # [2, 2, 2, 3, 3, 3, 3]
        counter = Counter(freqMap) # Counter({3: 4, 2: 3})

        return max(counter.values())