[Python3] Union Find + Math + Hash - Simple Solution
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \n\n# Complexity\n- Time 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity: $$O(NlogN)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(N)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass UnionFind:\n    \n    def __init__(self, n: int):\n        self.root = list(range(n))\n        self.rank = [1 for _ in range(n)]\n\n    def find(self, x: int) -> int:\n        if self.root[x] != x: self.root[x] = self.find(self.root[x])\n        return self.root[x]\n\n    def union(self, x: int, y: int) -> None:\n        rootx, rooty = self.find(x), self.find(y)\n        if rootx == rooty: return\n        if self.rank[rootx] > self.rank[rooty]: self.root[rooty] = rootx\n        elif self.rank[rootx] < self.rank[rooty]: self.root[rootx] = rooty\n        else:\n            self.root[rooty] = rootx\n            self.rank[rootx] += 1\n\n    def is_connected(self, x: int, y: int) -> bool:\n        return self.find(x) == self.find(y)\n\n\nclass Solution:\n    def largestComponentSize(self, nums: List[int]) -> int:\n        def get_prime_factors(n: int) -> List[int]:\n            s = set()\n            while n % 2 == 0:\n                s.add(2)\n                n //= 2\n            \n            for i in range(3, int(math.sqrt(n)) + 1, 2):\n                while n % i == 0:\n                    s.add(i)\n                    n //= i\n            \n            if n > 2: s.add(n)\n            return list(s)\n\n        uf = UnionFind(len(nums))\n        prime = collections.defaultdict(int)\n        for i, num in enumerate(nums):\n            primes = get_prime_factors(num)\n            for p in primes:\n                if p in prime: uf.union(prime[p], i)\n                prime[p] = i\n\n        c = collections.Counter()\n        for i in range(len(nums)): c[uf.find(i)] += 1\n\n        return max(c.values())\n```
['Hash Table', 'Math', 'Union Find', 'Python3']