Count how many prime numbers are strictly less than n.
The Sieve of Eratosthenes marks multiples of each prime as composite: start at 2, and for each unmarked number mark its multiples (starting from its square) as composite. Numbers still unmarked are prime. This is O(n log log n) — far faster than testing each number individually.
public static int countPrimes(int n) {
if (n < 2) return 0;
boolean[] composite = new boolean[n];
int count = 0;
for (int i = 2; i < n; i++) {
if (!composite[i]) {
count++;
for (long j = (long) i * i; j < n; j += i) composite[(int) j] = true;
}
}
return count;
}function countPrimes(n) {
if (n < 2) return 0;
const composite = new Array(n).fill(false);
let count = 0;
for (let i = 2; i < n; i++) {
if (!composite[i]) {
count++;
for (let j = i * i; j < n; j += i) composite[j] = true;
}
}
return count;
}def count_primes(n):
if n < 2:
return 0
composite = [False] * n
count = 0
for i in range(2, n):
if not composite[i]:
count += 1
for j in range(i * i, n, i):
composite[j] = True
return countThe sieve is the standard way to precompute primes for cryptography, hashing, and number-theory tooling — a big win over per-number primality tests.
Why start marking multiples from i*i instead of 2*i?