204. Count Primes - Detailed Explanation

Problem Statement

Given an integer n, count the number of prime numbers strictly less than n. A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself.

For example:

For n = 10, the primes less than 10 are 2, 3, 5, 7. Therefore, the output is 4.
For n = 0 or n = 1, there are no prime numbers, so the output is 0.

Hints

Sieve of Eratosthenes:
A well-known algorithm to efficiently find all prime numbers less than n is the Sieve of Eratosthenes. The idea is to start with a list of all numbers from 2 up to n-1 and iteratively mark the multiples of each prime as non-prime.
Marking Multiples:
When you find a prime number, mark all its multiples (starting from its square) as non-prime, because any smaller multiple would have been marked by a smaller prime factor already.
Optimization:
You only need to check for multiples up to the square root of n because if a number is composite, it must have a factor less than or equal to its square root.

Approaches

Sieve of Eratosthenes (Optimal)

Initialization:
Create a boolean array of size n, initially set all entries to True (except for indices 0 and 1 which are not prime).
Mark Non-prime Numbers:
Iterate i from 2 up to √n. For each number i that is still marked as prime, mark its multiples (starting from i²) as not prime.
Count the Primes:
Count the number of entries in the boolean array that remain True. This count gives the number of primes less than n.

Complexity Analysis

Time Complexity:
O(n log log n) due to the Sieve of Eratosthenes algorithm.
Space Complexity:
O(n) because of the boolean array used to mark primes.

Step-by-Step Walkthrough with Example

Consider n = 10:

Initialization:
Create an array isPrime of size 10 and set all indices 2 to 9 as True.
```
isPrime: [False, False, True, True, True, True, True, True, True, True]
```
(Indices 0 and 1 are False because 0 and 1 are not prime.)
Iteration:
- For i = 2 (prime):
  Mark multiples of 2 starting from 4 (2²). Mark indices 4, 6, 8 as False.
```
isPrime: [False, False, True, True, False, True, False, True, False, True]
```
- For i = 3 (prime):
  Mark multiples of 3 starting from 9 (3²). Mark index 9 as False.
```
isPrime: [False, False, True, True, False, True, False, True, False, False]
```
- For i = 4, i = 5, etc.:
  Since 4 is already marked as False, skip it. Continue until i > √10 (i > 3.16), so we stop after i = 3.
Count the Primes:
Count indices that are True: indices 2, 3, 5, 7 are True, so the count is 4.

Common Mistakes

Not Handling Edge Cases:
Ensure you handle n ≤ 2 properly (should return 0).
Starting Multiples Incorrectly:
When marking multiples, start at i² instead of 2*i because numbers less than i² would have been marked by smaller primes.
Memory Usage:
Ensure that the boolean array is correctly sized (n elements) to avoid off-by-one errors.

Python Code

Python3

. . . .

Java Code

Java

. . . .

Edge Cases

n = 0 or n = 1:
No prime numbers exist.
Small Values of n:
Verify that the algorithm correctly handles cases like n = 2 or n = 3.
Large n:
The Sieve algorithm scales well, but be mindful of the memory footprint when n is very large.