204. Count Primes
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
My Accepted Solution
n = number
Time complexity: O($nlg_2^2n$)
Space complexity: O(n)
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);
}
};