[Python] 1396ms, faster than official 2224ms method.
maybe you are curious about step 3. step 3 is to deal with the prime number which is larger than m ** 0.5. step 1,2,4 are very intuitive tbh. For the running ti
maybe you are curious about step 3. step 3 is to deal with the prime number which is larger than m ** 0.5. step 1,2,4 are very intuitive tbh. For the running time, they are not consistent for each run. I have submitted several times and below are the report.\na few seconds ago\tAccepted\t1396 ms\tpython\na few seconds ago\tAccepted\t1572 ms\tpython\na few seconds ago\tAccepted\t1836 ms\tpython\na few seconds ago\tAccepted\t1696 ms\tpython\na few seconds ago\tAccepted\t1396 ms\tpython\n3 minutes ago\tAccepted\t1408 ms\tpython\n3 minutes ago\tAccepted\t1448 ms\tpython\n3 minutes ago\tAccepted\t1944 ms\tpython\n4 minutes ago\tAccepted\t1536 ms\tpython\n4 minutes ago\tAccepted\t1648 ms\tpython\n4 minutes ago\tAccepted\t1384 ms\tpython\n\n\n```\nclass Solution(object):\n    def largestComponentSize(self, A):\n        """\n        :type A: List[int]\n        :rtype: int\n        """\n        parent = range(len(A))\n        # Union Find\n        def Findparent(i):\n            if parent[i] != i:\n                parent[i] = Findparent(parent[i])\n            return parent[i]\n\n        # step 1: Sieve of Eratosthenes, only consider the prime number <= m ** 0.5 \n        m = int(max(A) ** 0.5) + 1\n        R = [1] * m\n        prime = []\n        for i in xrange(2, m):\n            if R[i] == 1:\n                prime.append(i)\n            for j in xrange(i*i, m, i):\n                R[j] = 0\n        \n        # step 2: check every prime number and do some prunes to narrow the search space\n        B = range(len(A))\n        for p in prime:\n            tempB = []\n            L = -1\n            # print A, B, parent\n            for idx in B:\n                if A[idx] % p == 0:\n                    if L == -1:\n                        L = idx\n                        a = Findparent(L)\n                    else:\n                        b = Findparent(idx)\n                        parent[b] = a\n                    while A[idx] % p == 0:\n                        A[idx] /= p      \n                if A[idx] > p:\n                    tempB.append(idx)     \n            B = tempB\n        \n        # step 3: deal with the number with primes > m ** 0.5 as its factors\n        D = {}\n        for idx in B:\n            if A[idx] not in D:\n                D[A[idx]] = []\n            D[A[idx]].append(idx)\n        # print D\n        for i in D:\n            if len(D[i]) > 1:\n                a = Findparent(D[i][0])\n                for j in xrange(1,len(D[i])):\n                    b = Findparent(D[i][j])\n                    parent[b] = a\n               \n        # step 4: do the counting\n        D = {}\n        for i in xrange(len(parent)):\n            a = Findparent(i)\n            if a not in D:\n                D[a] = 0\n            D[a] += 1\n        return max(D.values())\n```
[]