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
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 ; } }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.