Easy C++ Solution 19ms - even numbers skipped


  • 0
    J

    I improved on the previous posts to skip even numbers.

    '''
    int countPrimes(int n) {

        if (n <= 2){
            return 0;
        }
        
        // 2 is the only even prime
        int count = 1;
        vector<bool> isprime(n, true);
        
        // skip the even numbers
        for (int i = 3; i < n; i += 2){
            if (isprime[i]){
                ++count;
                // again, skip the even numbers
                for (int j = i; j < n; j += 2 * i){
                    isprime[j] = false;
                }
            }
        }
        return count;
    }
    

    '''


Log in to reply
 

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