C++ O(NLogN) solution using DFS and Sieve of Eratosthenes | Easy to understand
In this approach, I\'m using Sieve of Eratosthenes to compute all the prime numbers till 10^5 and then store them in an array primelist. Then, I can compute uni
In this approach, I\'m using Sieve of Eratosthenes to compute all the prime numbers till 10^5 and then store them in an array `primelist`. Then, I can compute unique prime factors for each number in LogN using the `factors()` function. \n\nFor every unique prime factor of nums[i], if a previous number in the array had the same prime factor (hashmap `m` is used to store this information), then this number is connected to that node (Just that node is sufficient. No need to connect to all previous nodes that had this prime factor because we only to need to calculate the component size and hence all the connections need not to be made. If we try to connect all the edges, then the number of edges can be n^2 which is not at all feasible because n <= 10^4). if none of the previous numbers had the same prime factor, then this index is stored for that particular prime factor in the hashmap `m`.\n\nThe maximum number of unique prime factors that a number <= 10^5 is 6. So, the maximum number of edges in the graph is n * 6 which is feasible. \n\nNow, we can just run a simple DFS to calculate the maximum component size in the graph.\n\n```\nclass Solution {\nprivate:\n    vector<bool> sieve(int n) {\n        vector<bool> prime(n + 1);\n        for (int i = 0; i <= n; i++)\n            prime[i] = 1;\n        for (int p = 2; p * p <= n; p++) {\n            if (prime[p] == 1) {\n                for (int i = p * p; i <= n; i += p)\n                    prime[i] = 0;\n            }\n        }\n        prime[1] = prime[0] = 0;\n        return prime;\n    }\n    vector<int> factors(int n, vector<int> &primelist) {\n        vector<int> facs;\n        for (int i = 0; primelist[i] * primelist[i] <= n && i < primelist.size(); i++) {\n            if (n % primelist[i] == 0) {\n                facs.push_back(primelist[i]);\n                while (n % primelist[i] == 0) {\n                    n /= primelist[i];\n                }\n            }\n        }\n        if (n > 1) facs.push_back(n);\n        return facs;\n    }\n    void dfs(vector<vector<int>> &gr, int node, vector<int> &vis, int &compSize) {\n        if(vis[node]) return;\n        vis[node] = 1;\n        compSize++;\n        for(auto x : gr[node]) {\n            dfs(gr, x, vis, compSize);\n        }\n    }\npublic:\n    int largestComponentSize(vector<int>& nums) {\n        int n = nums.size();\n        vector<vector<int>> gr(n);\n        vector<bool> prime = sieve(1e5 + 6);\n        vector<int> primelist;\n\t\t// Getting all the primes till 10^5 as maximum value of nums[i] is 10^5\n        for (int i = 2; i <= 1e5 + 5; i++) if (prime[i]) primelist.push_back(i);\n        unordered_map<int, int> m; // to store the index of the node with prime factor x\n        for(int i = 0; i < n; i++) {\n            vector<int> facs = factors(nums[i], primelist);\n            for(auto j : facs) {\n                if(m.find(j) == m.end()) { // prime factor had not occured before\n                    m[j] = i; // j is the prime factor and its index is i\n                } else {\n\t\t\t\t    // prime factor has already been seen before in a previous number and nums[i] is connected to that number\n                    gr[i].push_back(m[j]);\n                    gr[m[j]].push_back(i);\n                }\n            }\n        }\n        int ans = 0;\n        vector<int> vis(n);\n        for(int i = 0; i < n; i++) { // running a simple dfs to calculate the maximum component size\n            if(!vis[i]) {\n                int compSize = 0;\n                dfs(gr, i, vis, compSize);\n                ans = max(ans, compSize);\n            }\n        }\n        return ans;\n    }\n};\n```
['Depth-First Search', 'Graph', 'C']