C++ 248ms, Simple Union-Find and Prime Decomposition
\n\nc++\nclass Solution {\npublic:\n    int largestComponentSize(vector<int>& A) {\n        int n = A.size();\n\n        for (int i = 0; i < n; i++) {\n        
\n\n```c++\nclass Solution {\npublic:\n    int largestComponentSize(vector<int>& A) {\n        int n = A.size();\n\n        for (int i = 0; i < n; i++) {\n            int a = A[i];\n            for (int j = 2; j * j <= a; j++) if (a % j == 0) {\n                vec[j].push_back(i + 1);\n                while (a % j == 0) a /= j;\n            }\n            if (a > 1) vec[a].push_back(i + 1);\n        }\n\n        djs.init(n);\n        for (int i = 2; i < MAXA; i++) if ((int) vec[i].size() >= 2) {\n            int temp = vec[i][0];\n            for (int j = 1; j < (int) vec[i].size(); j++) djs.merge(temp, vec[i][j]);\n        }\n\n        int ans = 1;\n        for (int i = 1; i <= n; i++) ans = max(ans, djs.size[djs.find(i)]);\n        return ans;\n    }\n\nprivate:\n    static constexpr int MAXA = 100005;\n    static constexpr int MAXN = 20005;\n    vector<int> vec[MAXA];\n\n    struct DJS {\n        int f[MAXN], size[MAXN];\n\n        void init(int n) {\n            for (int i = 1; i <= n; i++) {\n                f[i] = i;\n                size[i] = 1;\n            }\n        }\n\n        int find(int x) {\n            if (x == f[x]) return x;\n            size[f[x]] += size[x];\n            size[x] = 0;\n            return f[x] = find(f[x]);\n        }\n\n        void merge(int x, int y) {\n            x = find(x), y = find(y);\n            if (x == y) return;\n            f[y] = x;\n            size[x] += size[y];\n            size[y] = 0;\n        }\n    } djs;\n};\n```
[]