A prime is a number only divisible by 1 and itself. Write all numbers below n in a row. Take the first unmarked number: it is prime, so cross out all its multiples. Repeat. Whatever never gets crossed out is prime. This is the Sieve of Eratosthenes.
Return how many primes are less than n. Example: n = 10 → 4.
The problem
Return the number of primes strictly less than n.
Example 1
Input: n = 10
Output: 4
2, 3, 5, 7.
Constraints
0 ≤ n ≤ 5 × 10⁶
Pattern clues in the wording
→ All primes up to a bound
These clues point to Number Theory and Combinatorics: GCD, primes, modular arithmetic, fast power and counting formulas that turn loops into a few lines of math.
Stuck? Take one hint at a time
Solution · starter
class Solution {
public int countPrimes(int n) {
return 0;
}
}
Write your solution locally or in your editor for now. Pick Java, Python, C++, JavaScript or Go above: every solution on this page switches with it. The in-browser runner will run these tests right here.
boolean[] composite; for p while p² < n, mark multiples; count the rest from 2.
▶ Dry run: Sieve of Eratosthenesn = 10
0
0
1
1
2
2
3
3
4
4
5
5
6
6
7
7
8
8
9
9
Step 1/5Numbers 0 to 9. We start checking from 2.
Approach 1
class Solution {
public int countPrimes(int n) {
if (n < 3) return 0;
boolean[] composite = new boolean[n];
int count = 0;
for (int p = 2; p < n; p++) {
if (composite[p]) continue;
count++;
for (long m = (long) p * p; m < n; m += p) composite[(int) m] = true;
}
return count;
}
}
Verdict: Trial division per number is much slower.