LeetCode Solutions
204. Count Primes
Time: $O(n\log\log n)$ Space: $O(n)$
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);
}
};
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;
}
}
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)