C++ Sieve of Erastosthenes 219ms roughly O(n * log^2(n))
Solution runs on 219ms (maybe there is a little bit more room for improvement, like using rank on DSU).\nTime complexity: O((n * log(log(n))) * ackermann functi
Solution runs on 219ms (maybe there is a little bit more room for improvement, like using rank on DSU).\nTime complexity: O((n * log(log(n))) * ackermann function(|A|)). Where n is the max number in the array.\nA rough analysis would be around O(n * log^2(n)), assuming the ackermann would result in around O(log n).\nAlgorithm:\nUse Sieve of Erastosthenes to generate all primes.\nWhile doing this, for each number we are going to mark as non-prime number,\nwe can also check if the number is in our initial array.\nIf yes, merge them together.\n```\nclass Solution {\npublic:\n    int p[100100], sz[100100];\n    \n    int find(int x) {\n        return x == p[x] ? x : p[x] = find(p[x]);\n    }\n    \n    void merge(int x, int y) {\n        x = find(x);\n        y = find(y);\n        if(x == y) return;\n        sz[x] += sz[y];\n        p[y] = x;\n    }\n    \n    int largestComponentSize(vector<int>& A) {\n        bool mark[100100] = {0}, used[100100] = {0};\n        for(int x : A) {\n            mark[x] = 1;\n            p[x] = x;\n            sz[x] = 1;\n        }\n        // Sieve of erastosthenes\n        for(long long i = 2; i <= 100000; i++) {\n            if(!used[i]) {\n                int last = -1;\n                // i is a prime, union all numbers which has i as its factor.\n                for(long long j = i; j <= 100000; j += i) {\n                    used[j] = 1;\n                    if(mark[j]) {\n                        if(last != -1) merge(last, j);\n                        last = j;\n                    }\n                }\n            }\n        }\n        int ans = 0;\n        for(int x : A) ans = max(ans, sz[x]);\n        return ans;\n    }\n};\n```
[]