Summary of 2 C++ implementation


  • 0

    solution 1

       class Solution {
        public:
            int countPrimes(int n) {
                if(n<=2)  return 0;
                vector<bool>  check(n, false);
                
                int result=1;
                int upper=sqrt(n);
                for(int i=3; i<n; i+=2){
                    if(!check[i]){
                        result++;
                        if(i>upper) continue;
                        for(int j=i*i; j<n; j+=i){
                            check[j]=true;
                        }
                    }
                }
                return result;
            }
        };
    

    solution 2

    class Solution {
    public:
        int countPrimes(int n) {
            vector<bool>  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.