Largest Component Size by Common Factor | C++ | Using Sieve and Union
\nclass Solution {\npublic:\n\t/*function to get root or parent*/\n    int getRoot(vector<int>& root, int x)\n    {\n        if(x == root[x])\n            retur
```\nclass Solution {\npublic:\n\t/*function to get root or parent*/\n    int getRoot(vector<int>& root, int x)\n    {\n        if(x == root[x])\n            return x;\n        else\n            return root[x] = getRoot(root, root[x]); \n    }\n\t/*get all prime factors of x in a vector*/\n     vector<int> getPrimes(int x, vector<int>& s) {\n        vector<int> primes;\n        while (x > 1) {\n            int p = s[x];\n            if(p == 0)\n                p = x;\n            primes.push_back(p);\n\t\t\t// Edit: uncomment next 2 lines and comment last x/=p to remove duplicate same primes, taken from other solution.\n\t\t\t// while(x % p == 0)\n            //    x /= p;\n            x /= p;\n        }\n        return primes;\n    }\n\t/*union a and b by making roots same*/\n    void unions(int a, int b, vector<int>& root)\n    {\n        int aR = getRoot(root, a);\n        int bR = getRoot(root, b);\n        if(aR > bR)  // if a is greater, make root of b as a\n            root[bR] = root[aR];\n        else\n            root[aR] = root[bR];\n    }\n    int largestComponentSize(vector<int>& nums) {\n        int n=nums.size();\n        int i,j,M=0;\n\t\tint ans=1; //minimum answer can be 1.\n        for(i=0;i<n;i++)\n        {\n            M = max(M,nums[i]); // get the maximum number.\n        }\n        vector<int>sieve(M+1); // used for sieve of eratosthenes\n        vector<int>count(M+1);  // count_i stores the count of all numbers having root = i\n        vector<int>root(M+1);  // stores the root\n        for(i=0;i<=M;i++)\n        {\n            root[i] = i; // make each number its on root\n        }\n        for(i=2;i*i<=M;i++)\n        {\n            if(sieve[i]) // prime number will have 0 value\n                continue;\n            for(j=i*i;j<=M;j+=i)\n            {\n                sieve[j] = i; // the smallest prime value will be stored here\n            }\n        }\n        for(i=0;i<n;i++)\n        {\n            if(nums[i]==1) //ignore 1\n                continue;\n            vector<int>v = getPrimes(nums[i], sieve); //get the prime factors\n            for(j=0; j<v.size()-1; j++)\n            {\n                unions(v[j], v[j+1], root); // union them i.e make their root same.\n            }\n            unions(v[j], nums[i], root); // union the number with one of their factors\n        }\n        for(i=0;i<n;i++)\n        {\n            int r = getRoot(root, nums[i]); // find the root i.e. the bucket in which this number will fall\n            count[r]++; //increase the count of that bucket\n            ans = max(ans, count[r]); // check max\n        }\n        return ans; // return the ans\n    }\n};\n```
['Union Find', 'C']