[Python]484ms beats100% UnionFind+PrimeDecomposition explained
\tfrom collections import defaultdict\n\n   \n\tclass Solution:\n\t\tMAXA = 100001\n\t\tisPrime=[0 for _ in range(MAXA+1)]\n\t\tisPrime[0]=-1;isPrime[1]=-1 #0 a
\tfrom collections import defaultdict\n\n   \n\tclass Solution:\n\t\tMAXA = 100001\n\t\tisPrime=[0 for _ in range(MAXA+1)]\n\t\tisPrime[0]=-1;isPrime[1]=-1 #0 and 1 are not prime numbers\n\t\tfor i in range(2, MAXA):\n\t\t\tif isPrime[i]==0: #i is prime\n\t\t\t\tfor multiple in range(i*i,MAXA+1,i):\n\t\t\t\t\tif isPrime[multiple]==0:\n\t\t\t\t\t\tisPrime[multiple]=i\n\t\t\t\tisPrime[i] = i # let i store itself for consistency\n\n\t\tdef largestComponentSize(self, A: List[int]) -> int:\n\t\t\tlabel = defaultdict(int)\n\n\t\t\tdef findRoot(key):\n\t\t\t\tif label[key] > 0:\n\t\t\t\t\tlabel[key] = findRoot(label[key])\n\t\t\t\t\treturn label[key]\n\t\t\t\telse:\n\t\t\t\t\treturn key\n\n\t\t\tdef mergeRoot(k1, k2):\n\t\t\t\tr1, r2 = findRoot(k1), findRoot(k2)  \n\t\t\t\tif r1 != r2:\n\t\t\t\t\tr1, r2 = min(r1, r2), max(r1, r2)\n\t\t\t\t\tlabel[r1] += label[r2]\n\t\t\t\t\tlabel[r2] = r1\n\t\t\t\treturn r1\n\n\t\t\tfor x in A:\n\t\t\t\troot_id = 0\n\t\t\t\twhile Solution.isPrime[x]!=-1:\n\t\t\t\t\tp = Solution.isPrime[x]\n\t\t\t\t\troot_id = findRoot(p) if root_id == 0 else mergeRoot(root_id, p)\n\t\t\t\t\tx //= p\n\t\t\t\tlabel[root_id] -= 1\n\n\t\t\treturn -min(label.values())\n# Explaination\nDenote *MAXA = UpperBound(A)*\nIn solution.isPrime, the *smallest prime factor* of that number is stored, for prime numbers, the number itself is stored to keep consistency.\nThe Generation itself takes an upperbound of *NumberOfPrimesLessThan(MAXA)\\*MAXA* which is about *MAXA\\*log(MAXA)* for non-trivial *MAXA*.\nBy using that, we could decompose all the numbers simply by looking up the isPrime array recursivly, which would take about *O(log(MAXA)))* time for each prime factor decomposition.\nFor UnionFind, the merge and ~O(1) time since we maintain the UnionFind to be at most 2 layers, and the merge itself takes O(1) time, the overall time complexity for this solution is *O(N+MAXA\\*log(MAXA))*. \n\n# Why this is so fast\nDue to the nature of the leetcode judge machine, the precomputaion part is not counted for the total time spent if you put them in the class part, so the complexity is reduced to O(N) which makes it faster than most solutions. Which means if someone tried to manually calculate all the prime factors for every numebr from 2 to MAXA, he/she can be even faster than this answer, If you put the calculation os isPrime inside the function, it would take ~2000ms to finish,\n\n# Alternative solution [980ms beats 99.6%]\nIf you don\'t want to play dirty, here\'s another solution for you:\n```\nfrom collections import defaultdict\n\n\nclass Solution:\n    def largestComponentSize(self, A: List[int]) -> int:\n        small_primes = (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317)\n        label = defaultdict(int)\n       \n        def findRoot(key):\n            if label[key] > 0:\n                label[key] = findRoot(label[key])\n                return label[key]\n            else:\n                return key\n        \n        def mergeRoot(k1, k2):\n            r1, r2 = findRoot(k1), findRoot(k2)  \n            if r1 != r2:\n                r1, r2 = min(r1, r2), max(r1, r2)\n                label[r1] += label[r2]\n                label[r2] = r1\n            return r1\n\n        for x in A:\n            root_id = 0\n            t = sqrt(x) + 1\n            for p in small_primes:\n                if p > t:\n                    break\n                elif x % p == 0:\n                    root_id = findRoot(p) if root_id == 0 else mergeRoot(root_id, p)\n                    while x % p == 0:\n                        x //= p\n            if x != 1:\n                root_id = findRoot(x) if root_id == 0 else mergeRoot(root_id, x)\n            label[root_id] -= 1\n        \n        return -min(label.values())\n```\nIn this, we pre-calculated all primes that\'s smaller that *sqrt(MAXA)*, any number can\'t be divided by that must be a prime number, which means a new group, and can also be merged using UnionFind. \n\n\n\n\n
[]