C++ 92s solution


  • 0
    class Solution 
    {
    public:
        int countPrimes(int n) 
        {
            if(n <= 2)
                return 0;
                
            bool *prime = new bool[n];
            int i, j, k;
            
            for(i = 0; i < n; i++)
                prime[i] = true;
                
            for(i = 2; i < n; i++)
                if(prime[i] == true)
                    for(j = i; j+i < n; j += i)
                        prime[j+i] = false;
                        
            for(i = 2,k = 0; i < n; i++)
                if(prime[i])
                    k++;
                    
            return k;
        }
    };

  • 0
    L

    You can change the line "for(j = i; j+i < n; j += i)" to for(j = i * i; j+i < n; j += i) because all non-prime numbers less than i*i is already set to false


Log in to reply
 

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