[Accepted][Python] Prime Factorization + Union Find + Optimization
The idea is that we only establish sets tagged by prime numbers.\nAnd we combine these sets according to the factorization of numbers in list A.\nSo we can larg
The idea is that we only establish sets tagged by prime numbers.\nAnd we combine these sets according to the factorization of numbers in list A.\nSo we can largely reduce the number of elements in Union Find.\n\nFor example:\n```\nA = [3, 4, 5, 6, 12]\n3 = 3\n4 = 2*2\n5 = 5\n6 = 2*3\n12 = 2*2*3\n```\n\nAt the beginning, we have some empty sets tagged by prime numbers 2, 3, 5, etc:\nSET(tag = 2) has 0 elements.\nSET(tag = 3) has 0 elements.\nSET(tag = 5) has 0 elements.\n\nThen we check every number in the list A.\n3 has prime factors: 3, so SET(tag = 3) now has 1 element.\n\n4 has prime factors: 2, so SET(tag = 2) now has 1 element.\n\n5 has prime factors: 5, so SET(tag = 5) now has 1 element.\n\n6 has prime factors: 2 and 3, so SET(tag = 2) now has 2 element. And we combine SET(tag = 3) with SET(tag = 2). Now SET(tag =2) has 3 elements. SET(tag = 3) also has 3 elements. It is obvious because SET(tag =2) and SET(tag =3) are the same set now.\n\n12 has prime factors: 2 andd 3, so SET(tag = 2) now has 4 element. And we combine SET(tag = 3) with SET(tag = 2) if they are not combined before. In this case, they have been already combined. Also SET(tag = 3) has 4 elements since it represents the same set as SET(tag = 2) does.\n\nSET(tag = 2) has 4 elements.\nSET(tag = 3) has 4 elements.\nSET(tag = 5) has 1 elements.\n\nThe answer is 4.\n\nThe 9,592nd prime is 99,991. The 9,593rd prime is 100,003.\nSo by my method, we will have at most 9592 elements in the Union Find.\n\n2^17 = 131072 > 100000 and 2^16 = 65536. So a number under 10^5 has at most 16 factors. Actually numbers under 10^5 has 2.66 different prime factors on average. For Union Find, if m operations, either Union or Find, are applied to n elements, the total run time is O(m log n), where log is the iterated logarithm. (https://en.wikipedia.org/wiki/Proof_of_O(log*n)_time_complexity_of_union%E2%80%93find)\n\nSo considering this problem, the worst time complexcity is O(N m log n) = O (20000*2.66 * log2 9592) = O(703709).\n\n\n```\nclass Solution(object):\n    def largestComponentSize(self, A):\n        """\n        :type A: List[int]\n        :rtype: int\n        """\n        def prime(n):\n            if n <= 1:\n                return 0\n            for i in range(2,int(math.sqrt(n)+1)):\n                if n%i == 0:\n                    return 0\n            return 1\n\n        def find(x):\n            if x != UF[x]:\n                UF[x] = find(UF[x])\n            return UF[x]\n        \n        def union(x, y):\n            xx, yy = find(x), find(y)\n            if xx != yy:\n                sum_UF[xx] += sum_UF[yy]\n                UF[yy] = xx\n        \n        m = max(int((max(A))**0.5)+2, 3)\n        primes = []\n        for i in range(2,m+1):\n            if prime(i):\n                primes.append(i)\n                \n        sum_UF = {}\n        UF = {}\n        \n        for x in A:\n            if x == 1:\n                continue\n            tmp = x\n            prime_factors = []\n            i = 0\n            while (i < len(primes)) and (primes[i] <= tmp**0.5):\n                if tmp % primes[i] == 0:\n                    prime_factors.append(primes[i])\n                    while tmp % primes[i] == 0:\n                        tmp = tmp // primes[i]\n                i += 1\n            if tmp != 1:\n                prime_factors.append(tmp)\n            \n            for p in prime_factors:\n                if p not in UF:\n                    UF[p] = p\n                    sum_UF[p] = 0\n            \n            sum_UF[find(prime_factors[0])] += 1\n            if len(prime_factors) > 1:\n                for i in range(1,len(prime_factors),1):\n                    union(prime_factors[0], prime_factors[i])\n            \n        ans = 1\n        for x in sum_UF:\n            ans = max(ans,sum_UF[x])\n        return ans\n```
[]