[Python3] union-find
\nO(MlogM) using sieve\n\nclass UnionFind: \n    \n    def __init__(self, n):\n        self.parent = list(range(n))\n        self.rank = [1]*n\n        \n    de
\n`O(MlogM)` using sieve\n```\nclass UnionFind: \n    \n    def __init__(self, n):\n        self.parent = list(range(n))\n        self.rank = [1]*n\n        \n    def find(self, p): \n        if p != self.parent[p]: \n            self.parent[p] = self.find(self.parent[p])\n        return self.parent[p]\n    \n    def union(self, p, q): \n        prt, qrt = self.find(p), self.find(q)\n        if prt == qrt: return False \n        if self.rank[prt] > self.rank[qrt]: prt, qrt = qrt, prt\n        self.parent[prt] = qrt\n        self.rank[qrt] += self.rank[prt]\n        return True \n\n\nclass Solution:\n    def largestComponentSize(self, A: List[int]) -> int:\n        m = max(A)\n        uf = UnionFind(m+1)\n        seen = set(A)\n        \n        # modified sieve of eratosthenes \n        sieve = [1]*(m+1)\n        sieve[0] = sieve[1] = 0 \n        for k in range(m//2+1): \n            if sieve[k]: \n                prev = k if k in seen else 0\n                for x in range(2*k, m+1, k): \n                    sieve[x] = 0\n                    if x in seen: \n                        if prev: uf.union(prev, x)\n                        else: prev = x\n        return max(uf.rank)\n```\n\n**Related problems**\n[952. Largest Component Size by Common Factor](https://leetcode.com/problems/largest-component-size-by-common-factor/discuss/1546345/Python3-union-find)\n[1998. GCD Sort of an Array](https://leetcode.com/problems/gcd-sort-of-an-array/discuss/1445278/Python3-union-find)\n\nAlternative implemetation `O(Nsqrt(M))` assuming `O(1)` union & find.\n```\nclass Solution:\n    def largestComponentSize(self, nums: List[int]) -> int:\n        m = max(nums)\n        uf = UnionFind(m+1)\n        for x in nums: \n            for p in range(2, int(sqrt(x))+1): \n                if x%p == 0: \n                    uf.union(x, p)\n                    uf.union(x, x//p)\n        freq = Counter(uf.find(x) for x in nums)\n        return max(freq.values())\n```\n\nAlternative implementation using `spf` `O((M+N)logM)`\n```\nclass Solution:\n    def largestComponentSize(self, nums: List[int]) -> int:\n        m = max(nums)\n        spf = list(range(m+1))\n        for x in range(4, m+1, 2): spf[x] = 2\n        for x in range(3, int(sqrt(m+1))+1): \n            if spf[x] == x: \n                for xx in range(x*x, m+1, x): \n                    spf[xx] = x \n        \n        uf = UnionFind(len(nums))\n        mp = {}\n        for i, x in enumerate(nums): \n            while x > 1: \n                if spf[x] in mp: uf.union(i, mp[spf[x]])\n                else: mp[spf[x]] = i\n                x //= spf[x]\n        return max(uf.rank)\n```
['Python3']