Easy C++ Union Find Based Approach
\nclass Solution {\npublic:\n    int find(int x, vector<int> &parent)\n    {\n        if(x==parent[x])\n        {\n            return x;\n        }\n        ret
```\nclass Solution {\npublic:\n    int find(int x, vector<int> &parent)\n    {\n        if(x==parent[x])\n        {\n            return x;\n        }\n        return parent[x] = find(parent[x],parent);\n    }\n    void merge(int a,int b,vector<int> &parent,vector<int> &rank)\n    {\n        int pa = find(a,parent);\n        int pb = find(b,parent);\n        if(pa!=pb)\n        {\n            if(rank[pa]<rank[pb])\n            {\n                swap(pa,pb);\n            }\n            parent[pb] = pa;\n            if(rank[pa]==rank[pb])\n            {\n                rank[pa]++;\n            }\n        }\n    }\n    \n    unordered_set<int> get_factors(int n, vector<int> &sieve)\n    {\n        unordered_set<int> f;\n        while(n>1)\n        {\n            f.insert(sieve[n]);\n            n = n/sieve[n];\n        }\n        return f;\n    }\n    \n    int largestComponentSize(vector<int>& nums) {\n        int n = nums.size();\n        int maxx = *max_element(nums.begin(),nums.end());\n        vector<int> parent(maxx+1);\n        for(int i =0;i<=maxx;i++)\n        {\n            parent[i] = i;\n        }\n        vector<int> rank(maxx+1,0);\n        \n        //create the factor sieve\n        vector<int> sieve(maxx+1);\n        for(int i=0;i<=maxx;i++)\n        {\n            sieve[i] = i;\n        }\n        for(int i=2;(i*i)<=maxx;i++)\n        {\n            if(sieve[i]==i)\n            {\n                for(int j = i*i;j<=maxx;j+=i)\n                {\n                    if(sieve[j]==j)\n                    {\n                        sieve[j] = i;\n                    }\n                }\n            }\n        }\n        //\n        \n        for(int i=0;i<n;i++)\n        {\n            int curr = nums[i];\n            unordered_set<int> fac = get_factors(curr,sieve);\n            for(int f:fac)\n            {\n                merge(f,curr,parent,rank);\n            }\n        }\n        map<int,int> mp;\n        int ans= 1;\n        for(int i=0;i<n;i++)\n        {\n            int pc = find(nums[i],parent);\n            mp[pc]++;\n            ans = max(ans,mp[pc]);\n        }\n        return ans;\n    }\n};\n```
[]