Optimized C++ solution


  • 0
    D
    int countPrimes(int n) {
        
      if (n <= 2) return 0;
    
      bool* primes = new bool[n];
      int sqr = sqrt(n-1);
      for (int i = 3; i <= sqr; i += 2){
        if (primes[i] == false){
            for (int j = i * i; j < n; j += i)
                primes[j] = true;
        }
      }
      int sum = 1;
      for (int i = 3; i < n; i += 2)
          sum += (primes[i] == false) ? 1 : 0;
      return sum;
    }

  • 0
    C

    For the loop of j = i * i, perhaps you can have the increment condition as j += (2 * i).

    As i is odd, we have i * i is odd. We will then have i * i + i is even (can be skipped). Hence, we can go to i * i + i + i directly (as j = i * i, next number will be j + 2 * i).


  • 0
    B

    in the code, primes[i]==true means that i is not a prime, so I think the code is correct.


  • -4
    L
    This post is deleted!

Log in to reply
 

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