Solution
Approach 1: UnionFind
We will skip the explanation of how a DSU structure is implemented. Please refer to https://leetcode.com/problems/redundantconnection/solution/ for a tutorial on DSU.
Intuition
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.
Algorithm
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 unionfind 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.
Complexity Analysis

Time Complexity: where is the length of
A
, and . 
Space Complexity: .
Analysis written by: @awice.