Count Primes - Unveiling the Sieve of Eratosthenes (Java)

Introduction :
Today, we venture into the world of number theory with a classic problem: "Count Primes" (LeetCode #204). At first glance, counting primes might seem like a simple loop, but to do it efficiently for larger numbers, we need a smarter approach. This problem is the perfect introduction to a powerful algorithm called the Sieve of Eratosthenes. Let's uncover its elegant solution and understand its efficiency!
Understanding the Problem:
We are given an integer n
. Our task is to return the number of prime numbers that are strictly less than n
.
Important Definitions:
A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. (e.g., 2, 3, 5, 7, 11...).
Strictly less than
n
means we count primes up ton-1
.
Examples:
Input:
n = 10
Output:
4
Explanation: The primes less than 10 are 2, 3, 5, 7. (Total 4)
Input:
n = 0
- Output:
0
- Output:
Input:
n = 1
- Output:
0
- Output:
Constraints:
0 <= n <= 5 * 10^6
(This constraint immediately tells us a naive approach will be too slow!)
My Thought Process & Approach (The Sieve of Eratosthenes):
My initial thought for counting primes might be to loop from 2 up to n-1
, and for each number, check if it's prime by trying to divide it by all numbers up to its square root. This "trial division" method would be very slow for large n
(roughly O(N * sqrt(N))). Given n
can be up to 5 * 10^6, N * sqrt(N)
would be way too much!
This is where the Sieve of Eratosthenes comes to the rescue. It's an ancient, yet highly efficient, algorithm for finding all prime numbers up to a specified integer. The core idea is simple:
Assume All Numbers are Prime: Create a boolean array,
isprime
, of sizen
(orn+1
for 1-based indexing convenience), and initially mark all entries from 2 up ton-1
astrue
. (0 and 1 are not prime, so we can ignore them or mark them as false).Start with the First Prime (2):
- Since 2 is prime, all its multiples (4, 6, 8, 10, ...) cannot be prime. So, we iterate through its multiples (starting from
2*2
orp*p
for optimization) and mark them asfalse
in ourisprime
array.
- Since 2 is prime, all its multiples (4, 6, 8, 10, ...) cannot be prime. So, we iterate through its multiples (starting from
Move to the Next Unmarked Number: Find the next number
p
that is still markedtrue
in ourisprime
array. This numberp
must be prime (because if it had a smaller prime factor, it would have already been markedfalse
).Mark its Multiples: Once we find a prime
p
, we then mark all its multiples (p*p
,p*p + p
,p*p + 2p
, ...) asfalse
. We start marking fromp*p
because any smaller multiples (e.g.,2p
,3p
) would have already been marked by smaller prime factors (2, 3, etc.).Repeat: Continue this process for all numbers
p
up tosqrt(n)
. We only need to go up tosqrt(n)
because if a numberk
has a prime factor greater thansqrt(n)
, it must also have a prime factor smaller thansqrt(n)
, which would have already markedk
as non-prime.Count Primes: After the sieving process, simply iterate through the
isprime
array from 2 ton-1
and count how many entries are still markedtrue
.
This method efficiently eliminates composites, leaving only primes.
Java Code Implementation:
class Solution {
public int countPrimes(int n) {
boolean[] isprime = new boolean[n];
Arrays.fill(isprime,true);
if(n<2){
return 0;
}
for(int p = 2;p*p<n;p++){
if(isprime[p]){
for(int i =p*p;i<n;i=i+p){
isprime[i] = false;
}
}
}
int cnt =0;
for(int i =2;i<n;i++){
if(isprime[i]){
cnt++;
}
}
return cnt;
}
}
Time and Space Complexity Analysis:
Time Complexity: O(N log log N)
This is the remarkable efficiency of the Sieve of Eratosthenes. The outer loop runs up to
sqrt(N)
. The inner loop marks multiples. The sum of iterations for marking is roughlyN/2 + N/3 + N/5 + ...
for all primes up toN
, which mathematically approximates toN * log(log(N))
.This is significantly faster than O(N * sqrt(N)) and allows it to pass for
n
up to 5 * 10^6.
Space Complexity: O(N)
- We use a boolean array
isprime
of sizeN
. The space used grows linearly with the inputN
. This is necessary to keep track of the primality of all numbers up toN
.
- We use a boolean array
Subscribe to my newsletter
Read articles from Kaushal Maurya directly inside your inbox. Subscribe to the newsletter, and don't miss out.
Written by
