Count the number of prime numbers less than a non-negative number, n.
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
Constraints:
0 <= n <= 5 * 106
public class Solution {
public int CountPrimes(int n) {
var notPrime = new bool[n];
int count = 0;
for(int i=2;i<n;i++){
if(notPrime[i]==false){
count++;
}
for(int j= 2;j*i<n;j++){
notPrime[j*i]=true;
}
}
return count;
}
}Time Complexity: O(n) // it's more than n but approx to n.
Space Complexity: O(n)
