<p>You are given an integer array of unique positive integers <code>nums</code>. Consider the following graph:</p>

<ul>
	<li>There are <code>nums.length</code> nodes, labeled <code>nums[0]</code> to <code>nums[nums.length - 1]</code>,</li>
	<li>There is an undirected edge between <code>nums[i]</code> and <code>nums[j]</code> if <code>nums[i]</code> and <code>nums[j]</code> share a common factor greater than <code>1</code>.</li>
</ul>

<p>Return <em>the size of the largest connected component in the graph</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2018/12/01/ex1.png" style="width: 500px; height: 97px;" />
<pre>
<strong>Input:</strong> nums = [4,6,15,35]
<strong>Output:</strong> 4
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2018/12/01/ex2.png" style="width: 500px; height: 85px;" />
<pre>
<strong>Input:</strong> nums = [20,50,9,63]
<strong>Output:</strong> 2
</pre>

<p><strong class="example">Example 3:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2018/12/01/ex3.png" style="width: 500px; height: 260px;" />
<pre>
<strong>Input:</strong> nums = [2,3,6,7,4,12,21,39]
<strong>Output:</strong> 8
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= nums.length &lt;= 2 * 10<sup>4</sup></code></li>
	<li><code>1 &lt;= nums[i] &lt;= 10<sup>5</sup></code></li>
	<li>All the values of <code>nums</code> are <strong>unique</strong>.</li>
</ul>

class Solution {
public:
    vector<int>par;
    vector<int>rank;
    vector<int>prime;
    vector<int>pr;
    int find(int x) {
        if (par[x]==x) return x;
        return par[x] = find(par[x]);
    }
    bool Union(int x, int y) {
        int xset = find(x);
        int yset = find(y);
        if (xset != yset) {
            if (rank[xset] >= rank[yset]) {
                rank[xset]+= rank[yset];
                par[yset]= xset;
            }
            else {
                rank[yset]+= rank[xset];
                par[xset]= yset;
                
            }
            return true;
        }
        return false;
    }
    void Seive(int n) {
        prime.resize(n+1,1);
        prime[0] = 0;
        prime[1] = 0;
        for (int i=2;i<=n;i++) {
            if (prime[i]==1) {
                pr.push_back(i);
                for (int j=i+i;j<=n;j+=i) {
                    prime[j] = 0;
                }
            }
        }

    }
    bool isPrime(int x) {
        return prime[x]==1;
    } 
    int largestComponentSize(vector<int>& nums) {
        int n= nums.size();
        par.resize(n);
        Seive(100001);
       
        unordered_map<int,vector<int>>mp;
        for (int i=0;i<n;i++) par[i] = i; 
        rank.resize(n,1);
        for (int i=0;i<n;i++) {
            int num = nums[i];
            int onum = num;
           
            for (int j=0;j<pr.size();j++) {
                
                int q = pr[j];
                if (q>num) break;
                if (num%q==0) {
                    mp[q].push_back(i);
                    while (num%q==0) {
                        num = num/q;
                    }
                }

            }
            
        }
        // // union find between all ele in same group
        // for (auto [d,v]:mp) {
        //     cout << d <<": ";
        //     for (auto ele:v) cout <<ele<<" ";
        //     cout <<endl;
        // }

        for (auto [d,v]: mp) {
            if (v.size()>=2) {
                for (int i=1;i<v.size();i++) {
                    Union(v[i],v[i-1]);
                }
            }
        }
        int ans = 1;
        for (int i=0;i<n;i++) {
            ans = max(ans,rank[i]);
        }
        return ans;
    }
};
122628