C++ solution based on Sieve of Eratosthenes theory


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

  • 1
    L

    should that be i*i < n?


  • 0

    @liuauto No, equal sign is indispensable, suppose some square number like 9, 16, 25...


Log in to reply
 

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