# Count Primes
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/count-primes)
Canonical: https://scaleengineer.com/dsa/problems/count-primes
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Enumeration](https://scaleengineer.com/dsa/patterns/enumeration), [Number Theory](https://scaleengineer.com/dsa/patterns/number-theory)
**Data structures:** Array
**Companies:** [Accenture](https://scaleengineer.com/companies/accenture), [Cognizant](https://scaleengineer.com/companies/cognizant), [Intel](https://scaleengineer.com/companies/intel), [Tech Mahindra](https://scaleengineer.com/companies/tech-mahindra), [Walmart Labs](https://scaleengineer.com/companies/walmart-labs), [Wipro](https://scaleengineer.com/companies/wipro), [tcs](https://scaleengineer.com/companies/tcs), [Salesforce](https://scaleengineer.com/companies/salesforce), [Nokia](https://scaleengineer.com/companies/nokia)
---
## Problem
Given an integer `n`, return _the number of prime numbers that are strictly less than_ `n`.

**Example 1:**

**Input:** n = 10
**Output:** 4
**Explanation:** There are 4 prime numbers less than 10, they are 2, 3, 5, 7.

**Example 2:**

**Input:** n = 0
**Output:** 0

**Example 3:**

**Input:** n = 1
**Output:** 0

**Constraints:**

* `0 <= n <= 5 * 106`

# Approaches
## Brute Force Approach
Check each number from 2 to n-1 if it's prime by testing divisibility up to the square root of the number.
**Time:** O(n * sqrt(n)) · **Space:** O(1)
**Pros:** Simple to understand and implement; Works for small inputs; Minimal space requirement
**Cons:** Very inefficient for large numbers; Performs redundant calculations; Not suitable for the given constraints
### Explanation
For each number from 2 to n-1, we check if it's prime by testing if it's divisible by any number from 2 to its square root. If no number divides it evenly, it's prime.

```java
public int countPrimes(int n) {
    if (n <= 2) return 0;
    
    int count = 0;
    for (int num = 2; num < n; num++) {
        if (isPrime(num)) {
            count++;
        }
    }
    return count;
}

private boolean isPrime(int num) {
    for (int i = 2; i <= Math.sqrt(num); i++) {
        if (num % i == 0) {
            return false;
        }
    }
    return true;
}
```
### Algorithm
1. Initialize count as 0
2. For each number from 2 to n-1:
   - Check if the number is prime
   - If prime, increment count
3. To check if a number is prime:
   - Test divisibility from 2 to square root of the number
   - If any number divides evenly, return false
   - If no divisors found, return true

## Sieve of Eratosthenes
Use the Sieve of Eratosthenes algorithm to mark all non-prime numbers in a boolean array and count the remaining prime numbers.
**Time:** O(n * log(log(n))) · **Space:** O(n)
**Pros:** Much more efficient than brute force approach; Eliminates redundant calculations; Suitable for the given constraints; Handles large inputs efficiently
**Cons:** Requires extra space proportional to input size; May not be suitable for memory-constrained environments; Initial array creation might be expensive for very large n
### Explanation
The Sieve of Eratosthenes is an efficient algorithm for finding all prime numbers up to a given limit. We create a boolean array and initially mark all numbers as prime. Then we iterate from 2 to sqrt(n) and mark all multiples of each prime number as non-prime.

```java
public int countPrimes(int n) {
    if (n <= 2) return 0;
    
    boolean[] isPrime = new boolean[n];
    Arrays.fill(isPrime, true);
    isPrime[0] = isPrime[1] = false;
    
    for (int i = 2; i <= Math.sqrt(n); i++) {
        if (isPrime[i]) {
            for (int j = i * i; j < n; j += i) {
                isPrime[j] = false;
            }
        }
    }
    
    int count = 0;
    for (int i = 2; i < n; i++) {
        if (isPrime[i]) count++;
    }
    return count;
}
```
### Algorithm
1. Create a boolean array of size n, initialize all elements to true
2. Mark 0 and 1 as non-prime
3. For each number i from 2 to sqrt(n):
   - If i is marked prime:
     - Mark all its multiples starting from i*i as non-prime
4. Count all remaining numbers marked as prime

## Optimized Sieve of Eratosthenes
Optimize the classic Sieve of Eratosthenes by using a boolean array and implementing various optimizations like skipping even numbers.
**Time:** O(n * log(log(n))) · **Space:** O(n/2)
**Pros:** Most efficient approach for this problem; Uses half the space of classic sieve; Reduces number of operations significantly; Handles very large inputs efficiently
**Cons:** More complex implementation; Still requires significant memory for large n; Code is less readable than simpler approaches
### Explanation
This approach optimizes the classic Sieve of Eratosthenes by only considering odd numbers and using various other optimizations to reduce the number of operations.

```java
public int countPrimes(int n) {
    if (n <= 2) return 0;
    
    // Initialize the array for odd numbers only
    boolean[] isPrime = new boolean[(n + 1) / 2];
    Arrays.fill(isPrime, true);
    isPrime[0] = false; // 1 is not prime
    
    int count = 1; // Count 2 as prime
    int sqrt = (int) Math.sqrt(n);
    
    for (int i = 3; i < n; i += 2) {
        if (i > sqrt) break;
        if (!isPrime[i/2]) continue;
        
        // Mark multiples of i as non-prime
        for (int j = i * i; j < n; j += 2 * i) {
            if (j % 2 == 1) {
                isPrime[j/2] = false;
            }
        }
    }
    
    // Count remaining primes
    for (int i = 1; i < isPrime.length; i++) {
        if (isPrime[i]) count++;
    }
    
    return count;
}
```
### Algorithm
1. Create a boolean array for odd numbers only
2. Count 2 as the first prime number
3. For each odd number i from 3 to sqrt(n):
   - If i is prime:
     - Mark its odd multiples starting from i*i as non-prime
4. Count all remaining numbers marked as prime

# Solutions
### CSharp

```csharp
public class Solution { public int CountPrimes ( int n ) { var notPrimes = new bool [ n ]; int ans = 0 ; for ( int i = 2 ; i < n ; ++ i ) { if (! notPrimes [ i ]) { ++ ans ; for ( int j = i + i ; j < n ; j += i ) { notPrimes [ j ] = true ; } } } return ans ; } }
```

### Java

```java
class Solution {
public
  int countPrimes(int n) {
    boolean[] primes = new boolean[n];
    Arrays.fill(primes, true);
    int ans = 0;
    for (int i = 2; i < n; ++i) {
      if (primes[i]) {
        ++ans;
        for (int j = i + i; j < n; j += i) {
          primes[j] = false;
        }
      }
    }
    return ans;
  }
}

```

### JavaScript

```javascript
/** * @param {number} n * @return {number} */ var countPrimes = function (n) {
  let primes = new Array(n).fill(true);
  let ans = 0;
  for (let i = 2; i < n; ++i) {
    if (primes[i]) {
      ++ans;
      for (let j = i + i; j < n; j += i) {
        primes[j] = false;
      }
    }
  }
  return ans;
};

```

### Python

```python
class Solution : def countPrimes ( self , n : int ) -> int : primes = [ True ] * n ans = 0 for i in range ( 2 , n ): if primes [ i ]: ans += 1 for j in range ( i + i , n , i ): primes [ j ] = False return ans
```

### CPP

```cpp
class Solution { public: int countPrimes ( int n ) { vector < bool > primes ( n , true ); int ans = 0 ; for ( int i = 2 ; i < n ; ++ i ) { if ( primes [ i ]) { ++ ans ; for ( int j = i ; j < n ; j += i ) primes [ j ] = false ; } } return ans ; } };
```