Count Primes
MedPrompt
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: 0Example 3:
Input: n = 1
Output: 0
Constraints:
0 <= n <= 5 * 106
Approaches
3 approaches with complexity analysis and trade-offs.
Check each number from 2 to n-1 if it's prime by testing divisibility up to the square root of the number.
Algorithm
- Initialize count as 0
- For each number from 2 to n-1:
- Check if the number is prime
- If prime, increment count
- 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
Walkthrough
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.
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;}Complexity
Time
O(n * sqrt(n))
Space
O(1)
Trade-offs
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
Use the Sieve of Eratosthenes algorithm to mark all non-prime numbers in a boolean array and count the remaining prime numbers.
Algorithm
- Create a boolean array of size n, initialize all elements to true
- Mark 0 and 1 as non-prime
- 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
- If i is marked prime:
- Count all remaining numbers marked as prime
Walkthrough
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.
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;}Complexity
Time
O(n * log(log(n)))
Space
O(n)
Trade-offs
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
Optimize the classic Sieve of Eratosthenes by using a boolean array and implementing various optimizations like skipping even numbers.
Algorithm
- Create a boolean array for odd numbers only
- Count 2 as the first prime number
- 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
- If i is prime:
- Count all remaining numbers marked as prime
Walkthrough
This approach optimizes the classic Sieve of Eratosthenes by only considering odd numbers and using various other optimizations to reduce the number of operations.
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;}Complexity
Time
O(n * log(log(n)))
Space
O(n/2)
Trade-offs
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
Solutions
Solution
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 ; } }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; }}/** * @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;};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 ansclass 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 ; } };Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.