Problem
Count the number of prime numbers strictly less than a non-negative integer n.
Example
Input: 10
Output: 4
2, 3, 5, 7.Solution
Sieve of Eratosthenes. Mark multiples of each prime as composite.
def count_primes(n):
if n < 2:
return 0
is_prime = [True] * n
is_prime[0] = is_prime[1] = False
for i in range(2, int(n ** 0.5) + 1):
if is_prime[i]:
for j in range(i * i, n, i):
is_prime[j] = False
return sum(is_prime)function countPrimes(n) {
if (n < 2) return 0;
const isPrime = new Array(n).fill(true);
isPrime[0] = isPrime[1] = false;
for (let i = 2; i * i < n; i++) {
if (isPrime[i]) {
for (let j = i * i; j < n; j += i) isPrime[j] = false;
}
}
return isPrime.filter(Boolean).length;
}int countPrimes(int n) {
if (n < 2) return 0;
vector<bool> isPrime(n, true);
isPrime[0] = isPrime[1] = false;
for (int i = 2; i * i < n; i++) {
if (isPrime[i]) {
for (int j = i * i; j < n; j += i) isPrime[j] = false;
}
}
int count = 0;
for (bool p : isPrime) if (p) count++;
return count;
}public int countPrimes(int n) {
if (n < 2) return 0;
boolean[] isPrime = new boolean[n];
Arrays.fill(isPrime, true);
isPrime[0] = isPrime[1] = false;
for (int i = 2; i * i < n; i++) {
if (isPrime[i]) {
for (int j = i * i; j < n; j += i) isPrime[j] = false;
}
}
int count = 0;
for (boolean p : isPrime) if (p) count++;
return count;
}Complexity
- Time: O(n log log n)
- Space: O(n)
Explanation
Start marking composites at i*i (smaller multiples are already marked by smaller primes). Only need to check up to sqrt(n).
Comments
Join the discussion. Got a question, found an issue, or want to share your experience?