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

1. 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.

2. 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.

3. 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)

1. Initialization:
   Create a boolean array of size n, initially set all entries to True (except for indices 0 and 1 which are not prime).

2. 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.

3. 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:

1. 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.)

2. 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.

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