python solution || O(n*sqrt(max(nums))) time || O(max(nums)) space || union find || faster than 31%
\t# Union Find Set  \n\tclass UnionFindSet: \n\t\tdef init(self, n): \n\t\t\tself.parents = [i for i in range(n+1)]\n\t\t\tself.ranks = [1 for _ in range(n+1)]\
\t# Union Find Set  \n\tclass UnionFindSet: \n\t\tdef __init__(self, n): \n\t\t\tself.parents = [i for i in range(n+1)]\n\t\t\tself.ranks = [1 for _ in range(n+1)]\n\n\t\tdef find(self, u): \n\t\t\twhile u != self.parents[u]: \n\t\t\t\tself.parents[u] = self.parents[self.parents[u]]\n\t\t\t\tu = self.parents[u]\n\t\t\treturn u\n\n\t\tdef union(self, u, v): \n\t\t\tu_parent = self.find(u)\n\t\t\tv_parent = self.find(v)\n\t\t\tif u_parent == v_parent: \n\t\t\t\treturn False\n\n\t\t\tif self.ranks[u_parent] > self.ranks[v_parent]:   \n\t\t\t\tself.parents[v_parent] = u_parent\n\t\t\telif self.ranks[u_parent] < self.ranks[v_parent]: \n\t\t\t\tself.parents[u_parent] = v_parent\n\t\t\telif self.ranks[u_parent] == self.ranks[v_parent]: \n\t\t\t\tself.parents[v_parent] = u_parent\n\t\t\t\tself.ranks[u_parent] += 1\n\t\t\treturn True    \n\n\n\tclass Solution(object):\n\t\tdef largestComponentSize(self, nums):\n\t\t\t"""\n\t\t\t:type nums: List[int]\n\t\t\t:rtype: int\n\t\t\t"""\n\t\t\tmax_num = max(nums)\n\t\t\tunion_find_set = UnionFindSet(max_num+1)\n\n\t\t\tfor num in nums: \n\t\t\t\tsqrt_num = int(num**(1/2.0))+1\n\t\t\t\tfor i in range(2, sqrt_num): \n\t\t\t\t\tif num%i==0: \n\t\t\t\t\t\tunion_find_set.union(num, i) \n\t\t\t\t\t\tunion_find_set.union(num, num/i)\n\n\t\t\tfrom collections import defaultdict\n\t\t\tres = defaultdict(int)            \n\t\t\tfor num in nums: \n\t\t\t\tres[union_find_set.find(num)] += 1\n\t\t\t# print(res.values())    \n\t\t\treturn max(res.values())\n\n
[]