Approach 1: Union-Find
We will skip the explanation of how a DSU structure is implemented. Please refer to https://leetcode.com/problems/redundant-connection/solution/ for a tutorial on DSU.
Let , and . For each value , there is at most one prime factor dividing . Let's call 's "big prime" this , if it exists.
This means that there are at most unique prime divisors of elements in : the big primes correspond to a maximum of values, and the small primes are all less than , so there's at most of them too.
Factor each into prime factors, and index every occurrence of these primes. (To save time, we can use a sieve. Please see this article's comments for more details.)
Then, use a union-find structure to union together any prime factors that came from the same .
Finally, we can count the size of each component, by inspecting and counting the id of the component each belongs to.
Time Complexity: where is the length of
A, and .
Space Complexity: .
Analysis written by: @awice.