Count Primes Given an integer n
, return the number of prime numbers that are strictly less than 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
Count Primes Solutions
✅Time: O(n log log n)
✅Space: O(n)
C++
class Solution {
public:
int countPrimes(int n) {
if (n <= 2)
return false;
vector<bool> prime(n, true);
prime[0] = false;
prime[1] = false;
for (int i = 0; i < sqrt(n); ++i)
if (prime[i])
for (int j = i * i; j < n; j += i)
prime[j] = false;
return count(begin(prime), end(prime), true);
}
};
Java
class Solution {
public int countPrimes(int n) {
if (n <= 2)
return 0;
int ans = 0;
boolean[] prime = new boolean[n];
Arrays.fill(prime, 2, n, true);
for (int i = 0; i < Math.sqrt(n); ++i)
if (prime[i])
for (int j = i * i; j < n; j += i)
prime[j] = false;
for (final boolean p : prime)
if (p)
++ans;
return ans;
}
}
Python
class Solution:
def countPrimes(self, n: int) -> int:
if n <= 2:
return 0
isPrime = [False] * 2 + [True] * (n - 2)
for i in range(2, int(n**0.5) + 1):
if isPrime[i]:
for j in range(i * i, n, i):
isPrime[j] = False
return sum(isPrime)
Watch Tutorial
Checkout more Solutions here