204. Count Primes

2020, Nov 27 One min read

1. Description

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

2. Example

Example 1

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

Example 2

Input: n = 0
Output: 0

Example 3

Input: n = 1
Output: 0

3. Constraints

0 <= n <= $5 * 10^6$

4. Solutions

Math

n = number
Time complexity: O($nlg_2^2n$)
Space complexity: O(n)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution
{
public:
    // int countPrimes(int n)
    int countPrimes(int number)
    {
        if(number <= 1) return 0;

        vector<int> primeSifter(number, 1);
        primeSifter[0] = primeSifter[1] = 0;
        for(int i = 2; i <= sqrt(number); i++)
        {
            if(primeSifter[i])
            {
                for(int j = i + i; j < number; j += i)
                    primeSifter[j] = 0;
            }
        }

        return accumulate(primeSifter.begin(), primeSifter.end(), 0);
    }
};

Search

Tags