c++ 780ms solution (easy to understand)


  • 0
    class Solution {
    public:
        int countPrimes(int n) {
            if(n<3)
                return 0;
            if(n==3)
                return 1;
            vector<int> prime;
            prime.push_back(2);
            for(int i=2; i<n; i++)
            {
                bool isprime = true;
                for(auto j : prime)
                {
                    if(i%j==0)
                    {
                        isprime = false;
                        break;
                    }
                    else if(i<j*j)
                        break;
                }
                if(isprime)
                    prime.push_back(i);
            }
            return prime.size();
        }
    };

  • 0
    W

    If I remember correctly, 2 is a prime number! XD


  • 0

    @windsound2010 We need to count the number of prime numbers that < n, not <= n, so it seems strange. However, it is right. Thanks.


Log in to reply
 

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