Count Primes
Count Primes is a medium arrays & hashing problem solved with the math / number theory pattern.
The best approach, optimal (sieve of eratosthenes), runs in O(n log log n) time and O(n) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (trial division) up.
Problem
Given an integer n, return how many prime numbers are strictly less than n.
A prime is a whole number greater than 1 whose only positive divisors are 1 and itself.
Examples
Example 1
- Input
n = 20- Output
8- Why
- The primes below 20 are 2, 3, 5, 7, 11, 13, 17 and 19.
Example 2
- Input
n = 3- Output
1- Why
- Only 2 is a prime strictly less than 3.
Example 3
- Input
n = 1- Output
0- Why
- There are no primes below 1.
Constraints
0 <= n <= 5 * 10^6
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 12 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (trial division) | O(n √n) | O(1) |
| Optimal (Sieve of Eratosthenes) | O(n log log n) | O(n) |
1Brute force (trial division)
O(n √n)Each of the n numbers tries up to √n divisors.O(1)Only a counter and loop variables.Check every number from 2 to n - 1 on its own. A number m is prime when no d with d × d <= m divides it.
- For m from 2 to n - 1: try d = 2, 3, … while d × d <= m.
- If no d divides m, count it.
- Return the count.
class Solution {
public int countPrimes(int n) {
int count = 0;
for (int m = 2; m < n; m++) {
if (isPrime(m)) count++;
}
return count;
}
private boolean isPrime(int m) {
for (int d = 2; (long) d * d <= m; d++) {
if (m % d == 0) return false;
}
return true;
}
}class Solution:
def countPrimes(self, n: int) -> int:
count = 0
for m in range(2, n):
if self.isPrime(m):
count += 1
return count
def isPrime(self, m: int) -> bool:
d = 2
while d * d <= m:
if m % d == 0:
return False
d += 1
return Trueclass Solution {
public:
int countPrimes(int n) {
int count = 0;
for (int m = 2; m < n; m++) {
if (isPrime(m)) count++;
}
return count;
}
private:
bool isPrime(int m) {
for (int d = 2; (long long)d * d <= m; d++) {
if (m % d == 0) return false;
}
return true;
}
};function countPrimes(n) {
let count = 0;
for (let m = 2; m < n; m++) {
if (isPrime(m)) count++;
}
return count;
}
function isPrime(m) {
for (let d = 2; d * d <= m; d++) {
if (m % d === 0) return false;
}
return true;
}2Optimal (Sieve of Eratosthenes)
O(n log log n)Prime p crosses out about n / p numbers, and the sum of 1 / p over primes up to n grows like log log n.O(n)One boolean per number below n.Start by assuming every number from 2 to n - 1 is prime. Walk p upward; whenever p is still marked prime, cross out p × p, p × p + p, … up to n. Anything never crossed out is prime. Starting at p × p is safe because every smaller multiple of p has a smaller prime factor that already crossed it out.
- If n < 3, return 0.
- composite = boolean array of size n, all false.
- For p = 2 while p × p < n: if !composite[p], mark composite[j] for j = p × p, p × p + p, … < n.
- Count the indices 2 … n - 1 that are not composite.
class Solution {
public int countPrimes(int n) {
if (n < 3) return 0;
boolean[] composite = new boolean[n];
for (int p = 2; (long) p * p < n; p++) {
if (composite[p]) continue;
for (int j = p * p; j < n; j += p) composite[j] = true;
}
int count = 0;
for (int m = 2; m < n; m++) {
if (!composite[m]) count++;
}
return count;
}
}class Solution:
def countPrimes(self, n: int) -> int:
if n < 3:
return 0
composite = bytearray(n)
p = 2
while p * p < n:
if not composite[p]:
composite[p * p:n:p] = b'\x01' * len(range(p * p, n, p))
p += 1
return n - 2 - sum(composite[2:])class Solution {
public:
int countPrimes(int n) {
if (n < 3) return 0;
vector<bool> composite(n, false);
for (int p = 2; (long long)p * p < n; p++) {
if (composite[p]) continue;
for (int j = p * p; j < n; j += p) composite[j] = true;
}
int count = 0;
for (int m = 2; m < n; m++) {
if (!composite[m]) count++;
}
return count;
}
};function countPrimes(n) {
if (n < 3) return 0;
const composite = new Uint8Array(n);
for (let p = 2; p * p < n; p++) {
if (composite[p]) continue;
for (let j = p * p; j < n; j += p) composite[j] = 1;
}
let count = 0;
for (let m = 2; m < n; m++) {
if (!composite[m]) count++;
}
return count;
}Edge cases to test
- n = 0, 1 or 2: the answer is 0 (the bound is strict, so 2 itself is not counted when n = 2)
- n is itself a prime: it must not be counted
- The largest n, where testing every number one by one is too slow
Hints
Hint 1
To test one number m, you only need to try divisors up to √m. How expensive is that over all m < n?
Hint 2
Flip it around: instead of asking whether m has a divisor, let every prime cross out its own multiples.
Hint 3
When crossing out multiples of p, you can start at p × p, because smaller multiples were already crossed out by smaller primes.
FAQ
What is the best time complexity for Count Primes?
Optimal (Sieve of Eratosthenes) runs in O(n log log n) time and O(n) extra space. Prime p crosses out about n / p numbers, and the sum of 1 / p over primes up to n grows like log log n.
Which pattern does Count Primes use?
It is a arrays & hashing problem that uses the math / number theory pattern. Other problems with the same pattern: Bulb Switcher, Reaching Points, Water and Jug Problem.
Is there a brute force solution for Count Primes?
Yes. Brute force (trial division) takes O(n √n) time and O(1) space. Check every number from 2 to n - 1 on its own.
Which edge cases should I test for Count Primes?
n = 0, 1 or 2: the answer is 0 (the bound is strict, so 2 itself is not counted when n = 2); n is itself a prime: it must not be counted; The largest n, where testing every number one by one is too slow.