C++DFS uses Linear Sieve| Eratosthenes' Sieve & Prime Number Theory
Intuition\n Describe your first thoughts on how to solve this problem. \n2 kinds of sieve methods are implemented,. One is Linear Sieve which has elapsed time o
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n2 kinds of sieve methods are implemented,. One is Linear Sieve which has elapsed time only O(M) of the time complexity. The other is the famous Eratosthenes\' Sieve Method with TC O(M log log M).\n\nBased on the Sieve\'s result, DFS is the algorithm to solve this question. It is doable. Use the similar tricks like the sieve method to build up the adjacent list.\n\nPrime Number Theory can be used to reserve the memory allocation and speed up the code.\n\nPrime Number Theory says\nthe number of {primes <=M }~M/log(M)\n\n\n<!-- Describe your approach to solving the problem. -->\n# Visualize Eratosthenes\' Sieve\n[https://youtu.be/7GGhURLPnIs](https://youtu.be/7GGhURLPnIs)\n\n# Math explains Eratosthenes\' Sieve\n[Please Turn on English subtitles if neccessary]\n[https://youtu.be/GxoMWxXLKMc](https://youtu.be/GxoMWxXLKMc)\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n$$O(M)$$ where M=max(nums[:])\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n$$O(M)$$\n# Code using Linear Sieve & DFS\n```\nclass Solution {\npublic:\n    int n;\n    vector<bool> sieve;\n    vector<int> prime;\n    vector<vector<int>> commonFactor;\n    vector<int> num_state;\n\n    void linearSieve(int n) {\n        sieve.assign(n + 1, false);\n        prime.reserve((int)(n/log(n)));// Use Prime Number Theory\n        for (int i = 2; i <= n; i++) {\n            if (!sieve[i]) prime.push_back(i); // When not sieved, i is a prime\n            for (int j = 0; i * prime[j] <= n; j++) {\n                sieve[i * prime[j]] = true;\n                if (i % prime[j] == 0) break;\n            }\n        }\n    }\n\n    void build_commonFactor_path(vector<int>& nums, int M) {\n        num_state.assign(M + 1, 0);\n        commonFactor.resize(M + 1, vector<int>());\n\n        for (int x : nums)\n            num_state[x] = 1;\n\n        for (int p : prime) {//Probably M/log(M) primes\n            if (num_state[p] != 1)\n                num_state[p] = -1;\n\n            for (int i = p * 2; i <= M; i += p) {\n                if (num_state[i] == 1) {\n                    commonFactor[i].push_back(p);\n                    commonFactor[p].push_back(i);\n                }\n            }\n        }\n    }\n\n    void dfs(int i, int& sz) {\n        if (num_state[i] == 1)\n            sz++;\n        num_state[i] = 2;\n\n        for (int x : commonFactor[i]) {\n            if (num_state[x] == 1 || num_state[x] == -1) {\n                dfs(x, sz);\n            }\n        }\n    }\n\n    int largestComponentSize(vector<int>& nums) {\n        n = nums.size();\n        int M = *max_element(nums.begin(), nums.end());\n        linearSieve(M);\n        build_commonFactor_path(nums, M);\n        int ans = 0;\n        for (int i : nums) {\n            if (num_state[i] == 1) {\n                int sz = 0;\n                dfs(i, sz);\n                ans = max(ans, sz);\n            }\n        }\n        return ans;\n    }\n};\n\n\n```\n# Code using Eratosthenes\' Sieve  with TC O(M log log(M)). In real test, it is faster than the linear Sieve, since M is not large enough\n```\n    int n;\n    vector<int> prime;\n    vector<vector<int>> commonFactor;\n    vector<bool> isPrime;\n    \n    void Sieve(int n){//TC: O(n log log n)\n        isPrime.assign(n+1, 1);\n        isPrime[0]=isPrime[1]=0;\n        int&& n_sqrt=int(sqrt(n));\n        for(int i=2; i<=n_sqrt; i++){\n            if (isPrime[i]){\n                for(int j=i*i ; j<=n; j+=i)\n                    isPrime[j]=0;\n            }\n        }\n        prime.reserve((int)(n/log(n)));//Use Prime Number Theory\n        for(int i=2; i<=n; i++)\n            if (isPrime[i]) prime.push_back(i);\n    }\n```
['Depth-First Search', 'Number Theory', 'C++']