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
4. Solutions
Math
n = number
Time complexity: O(nlg$_2^2$n)
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);
}
};
|