C++ DSU through prime factorization
For each $ a_i $ in $ nums $, find its prime factorization $ p_1^{k_1} \cdot p_2^{k_2} \ldots p_m^{k_m} $. Then for each prime $ p $, check if it has already be
For each $ a_i $ in $ nums $, find its prime factorization $ p_1^{k_1} \\cdot p_2^{k_2} \\ldots p_m^{k_m} $. Then for each prime $ p $, check if it has already been associated with a previous element $ a_j $ in $ nums $. If it has, unite $ a_i $ and $ a_j $. \n\n```\nclass Solution {\n\nprivate:\n    struct DSU {\n        vector<int> e;\n        DSU() : e(2e5, -1) {}\n        int get(int x) { return e[x] < 0 ? x : get(e[x]); }\n        int sz(int x) { return -e[get(x)]; }\n        void unite(int x, int y) {\n            x = get(x), y = get(y);\n            if(x == y) return;\n            if(e[x] > e[y]) swap(x, y);\n            e[x] += e[y];\n            e[y] = x;\n        }\n    };\n\npublic:\n    int largestComponentSize(vector<int>& nums) {\n        vector<int> pset(2e5, -1);\n        DSU dsu;\n        int ans = 0;\n        for(auto a : nums) {\n            vector<int> p;\n            int tmp = a;\n            for(int i = 2; i * i <= tmp; i++) {\n                if(tmp % i == 0) {\n                    p.push_back(i);\n                    while(tmp % i == 0) {\n                        tmp /= i;\n                    }\n                }\n            }\n            if(tmp > 1) {\n                p.push_back(tmp);\n            }\n            for(auto pr : p) {\n                if(pset[pr] != -1) {\n                    dsu.unite(a, pset[pr]);\n                }\n                pset[pr] = a;\n            }\n            ans = max(ans, dsu.sz(a));\n        }\n        return ans;\n    }\n};\n```
['C++']