Python 3 FT 90%: Link Numbers to Prime Factors, Sieve of Eratosthenes, Trial Divide by <= Sqrt(n)
Intuition\n\nThis is basically the same solution as DBabichev\'s, just wanted to share the key insights needed to avoid TLE. There are lots of ways to get the r
# Intuition\n\nThis is basically the same solution as DBabichev\'s, just wanted to share the key insights needed to avoid TLE. There are lots of ways to get the right answer, but there are some nontrivial things you must do to avoid TLE. In my opinion the max runtime is bit too strict for this problem - this is more of a Project Euler problem than a LC problem!\n\nIn order of least obvious to most obvious, here\'s what matters for performance:\n* you MUST find unique prime factors of each number `n` with a method that only checks up to `sqrt(n)`. Otherwise you check up to `O(n)` which will give you TLE.\n* instead of literally adding `O(N^2)` edges, instead add an edge from each number `n` to each of its unique prime factors `p`. This way all numbers that share 1 or more prime factors are in the same component, but you add `log(n)` edges instead of `O(N)` edges for each number.\n  * union-find makes it easy to effectively add these edges, and nicely updates the clusters as you go\n* you benenfit from using the Sieve of Erathosthenes to memoize all primes you would do trial division with, a lot faster than trying 2, 3, 4, .., sqrt(n) every time. Saves a lot of divisions\n\n\n## Union Find\n\nSince the solution involves clusters, we can infer that union-find is going to be the cornerstone of our solution. If you\'re not familiar with union-find, PLEASE do yourself a favor and research it! It\'s a very important algorithm to know for interviews. Here are the highlights:\n* union-find finds connected components in a graph with N vertices and E edges in O(N+E) time. Same time complexity as DFS, but faster (less recursion overhead) and simpler\n* each node starts off in its own cluster, with no parent. Each node is its own root\n* a root node has no parent\n* to union two nodes, i.e. add an edge and unify their components\n  * find the roots of both nodes\n  * if the roots aren\'t the same, add the size of the smaller component to the larger component. This is called "union by rank" and is essential to guaranteeing O(N+E) time.\n* when finding the root of a node, we shortest the existing path of parent pointers as much as possible. This is called "path compression." It too is essential to guaranteenig O(N+E) time.\n  * the easiest way to to use recursion to find the root, then set `parent[node] = root`. This is easiest to write and it results in the shortest possible path at all times\n  * if you run out of stack space, you can switch to another approach where you set each node\'s parent to its grandparent in a loop. This only cuts the path length in half, but avoids recursion and any stack limit exceeded errors\n\n## What are the Nodes?\n\nWhile we could call `union(m, n)` for every pair of numbers with a common prime factor, that\'s `O(N^2)` calls so you\'ll get TLE.\n\nSo the solution instead is to use the transitive property:\n* instead of linking `m` directly to all other numbers `n` that share a prime factor, we\n* link each number `n` to its unique prime factors\n* that way each number `m` is connected via its prime factors to all other numbers `n` that share at least one prime factor\n\nSo we have a node for every number from 1 to `max(nums)`.\n\n## Finding Unique Prime Factors\n\n**This is IMO the hardest part:** if you don\'t do this exactly right then you\'ll get TLE, even using union-find.\n\nThere are two relatively simple ways to get all unqiue prime factors:\n* easiest: loop over primes from 2 until `n//2` and append them. If you don\'t find any primes, `n` itself is prime.\n* harder: the recursive version. If `n` is _not_ prime, it has a prime factor less than or equal to `sqrt(n)`.\n  * so do trial division by prime factors up to `sqrt(n)`\n  * if you find a prime, return the union of the prime and the prime factors of `n//prime` (recursion)\n  * if you don\'t find a prime less than or equal to `sqrt(n)`, then `n` itself is prime so return `{n}`\n\n**You have to use a variant of the second one.** The first one is $O(max(nums))$. Way too slow. The second one is $O(sqrt(max(nums)))$ which is obviously way faster since the max number is $10^5$.\n\nThe version I wrote does the following:\n* `uniqueFactors(i, n)` finds all unique factors in `primes[i:]` that divide `n`\n* if there is a prime less than `sqrt(n)` that divides `n`, I call `uniqueFactors(j, r)` to find all larger unique factors. Then I append `primes[i]` and return\n* if there is no prime factor up to `sqrt(n)` then `n` itself is prime\n\n## Getting Primes Up to sqrt(max(nums)) in the First Place\n\nTechnically yout don\'t need to do this: n the `uniqueFactors` function, you can trial divide by all integers in `2..sqrt(n)`.\n\nBut we know for example that all even numbers above 2 are not prime. Every multiple of 3 above 3 is not prime either. In general, every multiple of prime `p` above `p` is not prime.\n\nSo to speed that part up I did two things\n* to get all primes we\'d trial divide by in the first place, I used the Sieve of Eratosthenes. It\'s a pretty literal version of "for each prime `p`, record that all multiples of `p` above `p` are not prime."\n  * **IMPORTANT:** In the Sieve code, you only mark off multiples of `p` above `p*p`. This is because any lower multiple of `p` can be written as `p*f` where `f < p`. The Sieve algorithm already marked off multiples of `f < p` in earlier iterations. This is really important for not getting TLE in time-constrained problems relating to primes\n* the `uniqueFactors` code divides out all factors of the current prime `p`, then recurses with all larger factors. That way we don\'t re-check division by 2, 3, 5, etc. if we\'ve already checked primes up to some larger number.\n\n# Code\n```\nclass Solution:\n    def largestComponentSize(self, nums: List[int]) -> int:\n \n        # This problem\'s TLE threshold seems too low, you have to do the problem\n        # EXACTLY RIGHT (tm) or you fail.\n        #  In particular: you need to use the recursive form of finding unique\n        #  factors so you only need to check up to sqrt(n). That\'s knowledge that\'s\n        #  past what I consider to be good for LC.\n\n        # Overall idea:\n        #    > we want to link numbers together if they share a prime factor\n        #    > cluster questions are almost always union-find questions\n        #    > we can "transitively link" numbers as follows:\n        #       > link each number n to its first prime factor\n        #       > then link its prime factors together\n        #       > this looks like a 1D chain: n -- firstFactor -- secondFactor -- .. -- lastFactor\n        #    > by doing this for each number, n will be linked via its prime factor(s) to all\n        #      other n\' with the same factor\n        #    > using union-find lets us get away with adding fewer factors\n\n        M = max(nums)\n        U = M//2\n        P = [True]*(M+1)\n        primes = [2]\n        for c in range(3, U+1, 2):\n            if P[c]:\n                primes.append(c)\n                for m in range(c*c, U+1, 2*c):\n                    P[m] = False\n\n        print(primes)\n\n        def uniqueFactors(i: int, n: int) -> List[int]:\n            """\n            Returns unique prime factors in primes[i:] that divide n. \n            \n            PRE: n is not divisible by primes[:i]\n            \n            Factors are returned in descending order.\n            """\n            if n == 1:\n                return []\n\n            for j in range(i, len(primes)):\n                p = primes[j]\n\n                if p*p > n:\n                    break\n\n                if n % p == 0:\n                    r = n//p\n                    while r % p == 0:\n                        r //= p\n                    factors = uniqueFactors(j+1, r)\n                    factors.append(p)\n                    return factors\n\n            return [n]\n\n        parent = [-1]*(M+1)\n\n        def find(n: int) -> int:\n            if parent[n] < 0:\n                return n\n            else:\n                parent[n] = find(parent[n])\n                return parent[n]\n\n        def union(m: int, n: int) -> None:\n            rm = find(m)\n            rn = find(n)\n\n            if rm == rn:\n                return\n\n            if parent[rm] > parent[rn]:\n                rm, rn = rn, rm\n\n            parent[rm] += parent[rn]\n            parent[rn] = rm\n\n        for n in nums:\n            if n == 1:\n                continue\n\n            # link n to each of its prime factors, transitively linking it to\n            # all numbers that share a factor\n            fs = uniqueFactors(0, n)\n            # print(f"uniqueFactors(0, {n}) = {fs}")\n            prev = n\n            for f in fs:\n                union(f, prev)\n                prev = f\n\n        # find cluster with the largest membership\n        sizes = Counter(find(n) for n in nums)\n        return max(sizes.values())\n```
['Python3']