Python solution using Disjoint Set Union and Prime Factorization
Time Complexity: O(N log(M))\nSpace Complexity: O(M)\nwhere N is the number of element and M is the maximum value among all elements\n\nTo have a factor greater
**Time Complexity:** O(N log(M))\n**Space Complexity:** O(M)\nwhere N is the number of element and M is the maximum value among all elements\n\nTo have a factor greater than 1, two numbers must have common primes in their prime factorization. Using this information, we can merge elements having common primes with Disjoint Set Union\n\n```\nclass DSU:\n    def __init__(self, n):\n        self.parent = [i for i in range(n)]\n        self.ranks = [1 for i in range(n)]\n    \n    def find(self, u):\n        if self.parent[u] == u:\n            return u\n        self.parent[u] = self.find(self.parent[u])\n        return self.parent[u]\n    \n    def merge(self, u, v):\n        u, v = self.find(u), self.find(v)\n        if u == v:\n            return\n        \n        if self.ranks[u] < self.ranks[v]:\n            u, v = v, u\n        self.ranks[u] += self.ranks[v]\n        self.parent[v] = u\n\n\nclass PrimeFactorizer:\n    def __init__(self, mx):\n        self.spf = [i for i in range(mx)]\n        self.mx = mx\n        self.sieve()\n    \n    def sieve(self):\n        limit = int(sqrt(self.mx)) + 1\n        \n        for i in range(2, limit):\n            if self.spf[i] != i:\n                continue\n            for j in range(i*i, self.mx, i):\n                if self.spf[j] == j:\n                    self.spf[j] = i\n    \n    def getPrimes(self, n):\n        primes = []\n        \n        while n > 1:\n            prime = self.spf[n]\n            primes.append(prime)\n            while n % prime == 0:\n                n //= prime\n        \n        return primes\n\n\nclass Solution:\n    def largestComponentSize(self, nums: List[int]) -> int:\n        max_num = max(nums)\n        mp = defaultdict(list)\n        \n        dsu = DSU(len(nums))\n        prime_factorizer = PrimeFactorizer(max_num + 1)\n        \n        for idx, num in enumerate(nums):\n            for prime in prime_factorizer.getPrimes(num):\n                mp[prime].append(idx)\n        \n        for prime in mp:\n            for i in range(1, len(mp[prime])):\n                dsu.merge(mp[prime][i], mp[prime][i-1])\n        \n        return max(dsu.ranks)\n```
['Union Find']