Short, Quick & Clean C++ Solution


  • 0

    Short, quick and clean implementation of the Sieve of Eratosthenes algorithm (more info here: https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes).

    int countPrimes(int n) {
        if(n < 2) return 0;
        vector<bool> primes(n+1, true); //assume all n integers are prime.
        for(int i=2; i<=sqrt(n); ++i) //only need to check upto the sqrt().
            if(primes[i]) { //if i is prime, set all (larger) multiples of i to false.
               for(int j=i*i; j<=n; j+=i) primes[j]=false;
           }
        int count = 0; //Count all primes less than n.
        for(int i=2; i<n; ++i) if(primes[i]) count++;
        return count;
    }
    

Log in to reply
 

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