204. Count Primes
Problem Description
The problem requires us to find the count of prime numbers less than a given integer n
. Remember, a prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself.
Intuition
The solution is based on an ancient algorithm known as the "Sieve of Eratosthenes". The algorithm works by iteratively marking the multiples of each number starting from 2. Once all multiples of a particular number are marked, we move on to the next unmarked number and repeat the process.
Here's the step-by-step intuition:
- We start with a boolean array
primes
where each entry is set toTrue
, meaning we assume all numbers are primes initially. - Starting from the first prime number 2, we mark all of its multiples as
False
, since multiples of 2 cannot be primes. - We continue this process for the next unmarked number (which would be the next prime) and mark all of its multiples as
False
. - We repeat the process until we have processed all numbers less than
n
. - During the process, every time we encounter a number that's not marked as
False
, it means this number is a prime number, and we increment the counterans
.
This solution is efficient because once a number is marked as False
, it will not be checked again, which greatly reduces the number of operations needed compared to checking every number individually for primality.
Learn more about Math patterns.
Solution Approach
The implementation of the countPrimes
function follows the Sieve of Eratosthenes algorithm:
-
We initialize a list called
primes
filled withTrue
, representing all numbers from 0 ton-1
. Here,True
signifies that the number is assumed to be a prime number. -
We iterate over each number starting from 2 (the smallest prime number) using a for loop
for i in range(2, n):
. If the number is marked asTrue
in ourprimes
list, it is a prime, as it hasn't been marked as not prime by an earlier iteration (via its multiples). -
When we find such a prime number
i
, we increment our answer counterans
by 1, as we've just found a prime. -
To mark the multiples of
i
as not prime, we loop through a range starting fromi*2
up ton
(exclusive), in steps ofi
, using the inner loopfor j in range(i + i, n, i):
. The step ofi
makes sure we only hit the multiples ofi
. -
For each multiple
j
of the prime numberi
, we setprimes[j]
toFalse
to denote thatj
is not a prime. -
Continue the process until all numbers in our list have been processed.
-
Finally, we return
ans
, which now holds the count of prime numbers strictly less thann
.
Throughout the process, the use of the array primes
and the marking of non-prime numbers optimizes the approach and avoids unnecessary checks, making this a classic and time-efficient solution for counting prime numbers.
Here is the final code that implements this approach:
1class Solution:
2 def countPrimes(self, n: int) -> int:
3 if n < 2:
4 return 0
5 primes = [True] * n
6 ans = 0
7 for i in range(2, n):
8 if primes[i]:
9 ans += 1
10 for j in range(i * i, n, i):
11 primes[j] = False
12 return ans
In this implementation, notice how we optimized the inner loop's starting point from i + i
to i * i
. Since any multiple k * i
(where k < i
) would already have been marked False by a prime less than i
, it suffices to start marking from i * i
.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's illustrate the solution approach with a small example where n = 10
. We want to find the count of prime numbers less than 10.
Following the steps outlined in the solution approach:
-
We start by initializing a list
primes
that represents the numbers from 0 to 9. All the values are set toTrue
, indicating we assume they are prime until proven otherwise:1primes = [True, True, True, True, True, True, True, True, True, True]
-
We start checking numbers from 2 (the smallest prime number). Since
primes[2]
isTrue
, 2 is a prime number, so we increment our prime countans
. -
Now, we mark all multiples of 2 as not prime by setting their respective positions in the
primes
array toFalse
. This will mark 4, 6 and 8 as not prime:1primes = [True, True, True, True, False, True, False, True, False, True]
The prime count
ans
is now 1. -
The next number is 3, which is also
True
in theprimes
list, so we incrementans
again. We then mark all multiples of 3 asFalse
, affecting 6 and 9:1primes = [True, True, True, True, False, True, False, True, False, False]
The prime count
ans
is now 2. -
The next number is 4, which is
False
in theprimes
list, so we skip it. -
Then we check 5, which is
True
. Therefore, we incrementans
and mark its multiples (none within our range, as the first would be 10, which is outside our range).The prime count
ans
is now 3. -
Continuing this process, we check 6 (marked as not prime), 7 (prime), and 8 (not prime). When we reach 7, we mark it as prime and increment
ans
.The prime count
ans
is now 4. -
Finally, we process 9 (marked as not prime) and the
primes
list won't change anymore as there's no need to mark further multiples. -
Our final prime count
ans
is 4. Therefore, there are 4 prime numbers less than 10.
Here's a visualization of the primes
list after processing primes:
1primes = [True, True, True, True, False, True, False, True, False, False] 2 ^ ^ ^ ^ 3Indices: 2 3 4 5 6 7 8 9
At the indices where primes
list is True
(excluding the indices 0 and 1 since we start counting primes from 2), those numbers are the primes less than 10, and we count them up to get our answer, which is 4. This is how the Sieve of Eratosthenes algorithm works and the code from the solution approach implements this efficiently to count the number of prime numbers less than any given integer n
.
Solution Implementation
1class Solution:
2 def countPrimes(self, n: int) -> int:
3 if n < 3: # There are no prime numbers less than 2
4 return 0
5
6 # Initialize a list to track prime numbers.
7 # True means the number is initially assumed to be prime
8 is_prime = [True] * n
9 # Count the number of primes
10 prime_count = 0
11
12 # Start from the first prime number, which is 2
13 for current_number in range(2, n):
14 if is_prime[current_number]:
15 prime_count += 1 # Increment count if current number is prime
16
17 # Mark multiples of the current number as not prime
18 for multiple in range(current_number * 2, n, current_number):
19 is_prime[multiple] = False
20
21 # Return the total count of prime numbers found
22 return prime_count
23
1class Solution {
2 // Method to count the number of prime numbers less than a non-negative number, n.
3 public int countPrimes(int n) {
4 // Initialize an array to mark non-prime numbers (sieve of Eratosthenes).
5 boolean[] isPrime = new boolean[n];
6 // Assume all numbers are prime initially (except index 0 and 1).
7 Arrays.fill(isPrime, true);
8
9 // Counter for the number of primes found.
10 int primeCount = 0;
11
12 // Iterate through the array to find prime numbers.
13 for (int i = 2; i < n; i++) {
14 // Check if the number at current index is marked as prime.
15 if (isPrime[i]) {
16 // Increment the count as we found a prime.
17 primeCount++;
18
19 // Mark the multiples of the current number as non-prime.
20 for (int j = i * 2; j < n; j += i) {
21 isPrime[j] = false;
22 }
23 }
24 }
25
26 // Return the total count of prime numbers found.
27 return primeCount;
28 }
29}
30
1class Solution {
2public:
3 // Function to count the number of prime numbers less than a non-negative number, n
4 int countPrimes(int n) {
5 vector<bool> isPrime(n, true); // Create a vector of boolean values, filled with 'true', representing prime status
6 int primeCount = 0; // Initialize a count of prime numbers
7
8 // Use the Sieve of Eratosthenes algorithm to find all primes less than n
9 for (int i = 2; i < n; ++i) { // Start at the first prime, 2, and check up to n
10 if (isPrime[i]) { // If the number is marked as prime
11 ++primeCount; // Increment the count of primes
12 // Mark all multiples of i as not prime starting from i^2 to avoid redundant work (i * i can be optimized to skip non-primes)
13 for (long long j = (long long)i * i; j < n; j += i) {
14 isPrime[j] = false; // Mark the multiple as not prime
15 }
16 }
17 }
18 return primeCount; // Return the total count of primes found
19 }
20};
21
1/**
2 * Counts the number of prime numbers less than a non-negative number, n.
3 * Implements the Sieve of Eratosthenes algorithm for finding all prime numbers in a given range.
4 * @param {number} n - The upper limit (exclusive) up to which to count prime numbers.
5 * @return {number} The count of prime numbers less than n.
6 */
7const countPrimes = (n: number): number => {
8 // Initialize an array of boolean values representing the primality of each number.
9 // Initially, all numbers are assumed to be prime (true), except for indices 0 and 1.
10 let isPrime: boolean[] = new Array(n).fill(true);
11 let primeCount: number = 0;
12
13 // Loop through the array starting from the first prime number, 2.
14 for (let i: number = 2; i < n; ++i) {
15 if (isPrime[i]) {
16 // Increment the prime counter when a prime number is encountered.
17 ++primeCount;
18
19 // Mark all multiples of i as non-prime (false).
20 for (let multiple: number = i + i; multiple < n; multiple += i) {
21 isPrime[multiple] = false;
22 }
23 }
24 }
25
26 // Return the count of prime numbers found.
27 return primeCount;
28};
29
Time and Space Complexity
Time Complexity
The time complexity for this Sieve of Eratosthenes algorithm is O(n log(log n))
. This is because the inner loop for marking the multiples as non-primes runs n/i
times for each prime number i
, and the sum of these series approximates n
multiplied by the harmonic series, which tends to log(log n)
as n
approaches infinity.
Space Complexity
The space complexity of the algorithm is O(n)
due to the primes
list which stores a boolean for each number up to n
to indicate whether it's a prime number or not.
Learn more about how to find time and space complexity quickly using problem constraints.
What are the two properties the problem needs to have for dynamic programming to be applicable? (Select 2)
Recommended Readings
Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.