Python | Union Find | Simple Solution
\nimport math\n\n\nclass DisjointSet:\n    def __init__(self, vertices):\n        self.parent = {}\n        self.rank = {}\n        for vertex in range(len(vert
```\nimport math\n\n\nclass DisjointSet:\n    def __init__(self, vertices):\n        self.parent = {}\n        self.rank = {}\n        for vertex in range(len(vertices)):\n            self.parent[vertex] = vertex\n            self.rank[vertex] = 0\n\n    def find(self, u):\n        if self.parent[u] != u:\n            self.parent[u] = self.find(self.parent[u])\n        return self.parent[u]\n\n    def union(self, u, v):\n        x = self.find(u)\n        y = self.find(v)\n        if x != y:\n            if self.rank[x] > self.rank[y]:\n                self.parent[y] = x\n            elif self.rank[y] > self.rank[x]:\n                self.parent[x] = y\n            else:\n                self.parent[y] = x\n                self.rank[x] += 1\n        \n        \nclass Solution:\n    def getPrimesFactors(self, num):\n        for i in range(2, int(math.sqrt(num))+1):\n            if num % i == 0:\n                return self.getPrimesFactors(num//i) | {i}\n        return {num}\n\n    def largestComponentSize(self, nums: List[int]) -> int:\n        primeFactors = {}\n        for index, num in enumerate(nums):\n            for prime in self.getPrimesFactors(num):\n                if prime in primeFactors:\n                    primeFactors[prime].append(index)\n                else:\n                    primeFactors[prime] = [index]\n\n        djs = DisjointSet(nums)\n        for indexes in primeFactors.values():\n            for index in range(len(indexes) - 1):\n                djs.union(indexes[index], indexes[index + 1])\n\n        longestConnectedComponentLength = 1\n        components = {}\n        for index in range(len(nums)):\n            x = djs.find(index)\n            if x in components:\n                components[x] += 1\n                longestConnectedComponentLength = max(longestConnectedComponentLength, components[x])\n            else:\n                components[x] = 1\n\n        return longestConnectedComponentLength\n\n```
['Union Find', 'Python']