204. Count Primes

Count the number of prime numbers less than a non-negative number, n.

Example:

Input: 10
Output: 4
Explanation: There are 4 prime numbers less than 10, they are 2, 3, 5, 7.

Solution

Approach 1: A number's times are not prime.

Code (Python)

Approach 1:

Code (C++)

Approach 1:

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