O(N) prime check Euler Sieve


  • 0
    F

    Here is the Euler Sieve method :

    Solution

    class Solution {
    public:
        int countPrimes(int n) {
            if (n == 0) return 0;
            vector<bool> flag(n, false);
            vector<int> p(n, 0);
            int index = 0;
            flag[0] = true, flag[1] = true;
            for (int i = 2; i <= n; i++) {
                if (!flag[i]) p[index++] = i;
                for (int j = 0; i * p[j] <= n; j++) {
                    flag[i*p[j]] = true;
                    if (i % p[j] == 0) break;
                }
            }
            return count(flag.begin(), flag.end(), false);
        }
    };
    

    The original solution is like this :

    class Solution {
    public:
        int countPrimes(int n) {
            if (n == 0) return 0;
            vector<int> prime(n, true);
            prime[0] = false, prime[1] = false;
            for (int i = 0; i < sqrt(n); i++) {
                if (prime[i]) {
                    for (int j = i*i; j < n; j += i) {
                        prime[j] = false;
                    }
                }
            }
            return count(prime.begin(), prime.end(), true);
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.