Count all prime numbers

[Question] Count all prime numbers from given n
Example

Input: n = 10
Output: 4
Explanation: There are 4 prime numbers less than 10, they are 2, 3, 5, 7.
Solution: using Sieve of Eratosthenes Algo
The Sieve of Eratosthenes is an ancient and efficient algorithm for finding all prime numbers up to a specified integer \( n \). It works by iteratively marking the multiples of each prime starting from 2, effectively sieving out the non-prime numbers. Here's how it works step by step:

1. **Initialization**: Create a boolean array `isPrime` of size `n`, initially setting all values to `true`. This array will serve as our sieve. We'll mark numbers as `false` if they are not prime.

2. **Starting with 2**: 2 is the first prime number. Mark all of its multiples as `false` in the `isPrime` array, starting from \(2^2\), \(2^2 + 2\), \(2^2 + 4\), and so on up to \(n\). This step will eliminate all even numbers greater than 2, except for 2 itself.

3. **Next prime**: Find the next number in the array that is still marked as `true`. This will be the next prime number. Let's call it \( p \).

4. **Mark multiples of \( p \)**: Starting from \( p^2 \), mark all multiples of \( p \) as `false` in the `isPrime` array. These multiples are \( p^2 \), \( p^2 + p \), \( p^2 + 2p \), and so on, up to \( n \).

5. **Repeat**: Repeat steps 3 and 4 until \( p^2 \) is greater than or equal to \( n \). At this point, all remaining `true` values in the `isPrime` array correspond to prime numbers.

6. **Counting the primes**: Finally, count the number of `true` values in the `isPrime` array. Each `true` value represents a prime number less than \( n \).

Let's demonstrate this with an example for \( n = 20 \):

1. **Initialization**:
   - Create `isPrime` array: `[true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true]`

2. **Starting with 2**:
   - Mark multiples of 2 as `false`: `[true, true, true, true, false, true, false, true, false, true, false, true, false, true, false, true, false, true, false, true]`

3. **Next prime (3)**:
   - Mark multiples of 3 as `false`: `[true, true, true, true, false, true, false, true, false, false, false, true, false, true, false, true, false, false, false, true]`

4. **Next prime (5)**:
   - Mark multiples of 5 as `false`: `[true, true, true, true, false, true, false, true, false, false, false, true, false, true, false, true, false, false, false, false]`

5. **Next prime (7)**:
   - \(7^2 = 49\) is greater than 20, so we stop.

6. **Counting the primes**:
   - Count the number of `true` values: `[true, true, true, true, false, true, false, true, false, false, false, true, false, true, false, true, false, false, false, false]`
   - There are 8 `true` values, so the number of primes less than 20 is 8.

// TC: O(loglog(n))
// SC: O(n)
class Solution {
    func countPrimes(_ n: Int) -> Int {
        
        guard n > 2 else { return 0 }
        
        var count = 0
        var isPrimeArray = Array(repeating: true, count: n)
        isPrimeArray[0] = false
        isPrimeArray[1] = false
        
        var current = 2
        
        // Sieve of Eratosthenes algorithm
        while current * current < n {
            if isPrimeArray[current] {
                var multiple = 2
                while current * multiple < n {
                    isPrimeArray[current * multiple] = false
                    multiple += 1
                }
            }
            current += 1
        }
        
        // Count the prime numbers
        for i in 2..<n {
            if isPrimeArray[i] {
                count += 1
            }
        }
        
        return count
    }
}