<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>

int find(int i,vector<int>&parent){
        if(parent[i]!=i){
            return parent[i]=find(parent[i],parent);
        }
        return parent[i];
    }
    void union2(int a,int b,vector<int>&parent,vector<int>&size){
        int i=find(a,parent);
        int j=find(b,parent);
       // cout<<i<<" "<<j<<" "<<size[i]<<" "<<size[j]<<endl;
        if(i==j){
            return;
        }
        if(size[i]>size[j]){
            size[i]+=size[j];
            parent[j]=i;
        }
        else{
            size[j]+=size[i];
            parent[i]=j;
        }
      //  cout<<i<<" "<<j<<" "<<size[i]<<" "<<size[j]<<endl;
    }


class Solution {
public:

    vector<int> helper(int n){
        vector<int>dp(n+1);
        for(int i=0;i<=n;i++){
            dp[i]=i;
        }
        for(int i=2;i*i<=n;i++){
            if(dp[i]!=i){
                continue;
            }
            for(int j=i*2;j<=n;j+=i){
                if(dp[j]==j){
                    dp[j]=i;
                }
            }
        }
        return dp;
    }
    int largestComponentSize(vector<int>& nums) {
        int n=nums.size();
        int a=nums[0];
        map<int,int>h;
        for(int i=0;i<n;i++){
            a=max(a,nums[i]);
            h[nums[i]]=1;
        }
        vector<int>dp=helper(a);
        vector<int>parent(a+1);
        vector<int>size(a+1,0);
        for(int i=0;i<=a;i++){
            parent[i]=i;
            if(h.count(i)){
                size[i]++;
            }
        }
        for(int i=0;i<n;i++){
            int a=nums[i];
            while(a>1){
                int b=dp[a];
                union2(nums[i],b,parent,size);
                while(a%b==0){
                    a/=b;
                }
               // a/=b;
            }
        }
        int c=0;
        for(int i=0;i<=a;i++){
            c=max(c,size[i]);
        }
        return c;
    }
   /* vector<int> helper(int n) {
        vector<int> spf(n + 1);
        for (int i = 1; i <= n; i++) spf[i] = i;
        for (int i = 2; i * i <= n; i++) {
            if (spf[i] == i) {
                for (int j = i * i; j <= n; j += i) {
                    if (spf[j] == j) spf[j] = i;
                }
            }
        }
        return spf;
    }

    int largestComponentSize(vector<int>& nums) {
        int maxNum = *max_element(nums.begin(), nums.end());
        vector<int> spf = helper(maxNum);

        vector<int> parent(maxNum + 1);
        vector<int> size(maxNum + 1, 0);

        for (int i = 1; i <= maxNum; i++) parent[i] = i;
        for (int num : nums) size[num] = 1;

        for (int num : nums) {
            int factor = num;
            while (factor > 1) {
                int primeFactor = spf[factor];
                union2(num, primeFactor, parent, size);
                while (factor % primeFactor == 0) {
                    factor /= primeFactor;
                }
            }
        }

        int maxSize = 0;
        vector<int> rootCount(maxNum + 1, 0);

        for (int num : nums) {
            int root = find(num, parent);
            rootCount[root] += 1;
            maxSize = max(maxSize, rootCount[root]);
        }

        return maxSize;
    }*/
};
98601