Simple C++ UF without primes
Fairly minimal C++ solution without unnecessary cruft like finding all primes, etc\n\nI\'m using UF indices 1..100000  to represent factors (initially all havin
Fairly minimal C++ solution without unnecessary cruft like finding all primes, etc\n\nI\'m using UF indices 1..100000  to represent factors (initially all having size=0) and 100001+i to represent the element A[i] (with initial size=1). I brute force all factors of each A[i] on the fly as I iterate through A and merge() them with the element\'s index:\n\n```\nclass Solution {\n    int parent[121000], size[121000];\n\npublic:\n    int largestComponentSize(vector<int>& A) {\n        for (int i = 0; i < 121000; i++) parent[i] = i;\n        memset(size, 0, sizeof(size));\n\n        for (int i = 0; i < A.size(); i++) {\n            size[100001 + i] = 1;\n            for (int p = 2; p*p <= A[i]; p++) {\n                if (A[i] % p == 0) {\n                    merge(p, 100001+i);\n                    merge(A[i]/p, 100001+i);\n                }\n            }\n            merge(A[i], 100001+i);\n        }\n\n        int max_cc = 1;\n        for (int i = 0; i < A.size(); i++)\n            max_cc = max(max_cc, size[find(100001+i)]);\n        return max_cc;\n    }\n\n    int find(int i) {\n        if (parent[i] != i) parent[i] = find(parent[i]);\n        return parent[i];\n    }\n\n    void merge(int i, int j) {\n        i = find(i);\n        j = find(j);\n        if (i == j) return;\n        size[i] += size[j];\n        parent[j] = i;\n    }\n};\n```
[]