Python 1032ms beat 100% time & space
Step 1: get primes less than sqrt(max(A))\nStep 2: compute factors for each number in A\nStep 3: use union-find to link two primes if they are factors of the sa
**Step 1: get primes less than sqrt(max(A))\nStep 2: compute factors for each number in A\nStep 3: use union-find to link two primes if they are factors of the same number in A\nStep 4: for each number in A, add to its union (the union represented by its smallest prime)**\n```\nclass Solution:\n    def largestComponentSize(self, A: List[int]) -> int:\n        primes = []\n        for x in range(2, int(max(A)**0.5)+1):\n            for y in primes:\n                if x % y == 0:\n                    break\n            else:\n                primes.append(x)\n    \n        factors = collections.defaultdict(list)         # compute factors of each \'a\'\n        for a in A:\n            x = a\n            for p in primes:\n                if p*p > x:\n                    break\n                if x % p == 0:\n                    factors[a].append(p)\n                    while x % p == 0:\n                        x //= p\n            if x > 1:                                   # a new prime found\n                factors[a].append(x)\n                primes.append(x)\n                \n        primes = list(set(primes))\n        n = len(primes)\n        p2i = {p: i for i,p in enumerate(primes)}       # prime to index\n        \n        parent = [i for i in range(n)]                  # union-find on primes\n        \n        def find(i):\n            if i != parent[i]:\n                parent[i] = find(parent[i])\n            return parent[i]\n        \n        def union(i,j):\n            pi, pj = find(i), find(j)\n            if pi != pj:\n                parent[pi] = pj\n\n        for a in A:\n            if factors[a]:\n                p0 = factors[a][0]\n                for p in factors[a][1:]:                # link two primes if they are factors of \'a\'\n                    union(p2i[p0], p2i[p])\n        \n        count = collections.Counter(find(p2i[factors[a][0]]) for a in A if factors[a])      # each \'a\' corresponds to a prime index\n        return max(count.values())\n```
['Union Find', 'Python']