c++ sieve of Eratosthenes


  • 0

    time complexity: O(n * long(log(n)))

    int countPrimes(int n) {
        vector<int> prime(n, 1);
        int res = max(0, n - 2);
        for (int i = 2; i < n; ++i) {
            if (prime[i] == 1) {
                for (int j = i + i; j < n; j += i) {
                    res -= prime[j];
                    prime[j] = 0;
                }
            }
        }
        return res;
    }
    

Log in to reply
 

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