Count Primes Solution for TCS NQT
Company: TCS NQT · Difficulty: Easy · Topics: Mathematics, Number Theory
Problem Statement
Given an integer n, return the number of prime numbers that are strictly less than n.
A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself.
Examples
Example 1:
Input: n = 10
Output: 4
Explanation: There are 4 prime numbers less than 10: 2, 3, 5, 7.
Example 2:
Input: n = 0
Output: 0
Explanation: There are no prime numbers less than 0.
Example 3:
Input: n = 1
Output: 0
Explanation: There are no prime numbers less than 1.
Example 4:
Input: n = 20
Output: 8
Explanation: There are 8 prime numbers less than 20: 2, 3, 5, 7, 11, 13, 17, 19.
Intuition
The most efficient way to find all prime numbers up to n is using the Sieve of Eratosthenes algorithm. This algorithm works by:
1. Creating a boolean array of size n, initially marking all numbers as prime
2. Starting from 2, mark all multiples of each prime number as non-prime
3. Count the remaining prime numbers
The key insight is that if a number is prime, all its multiples (except itself) are composite.
Approach
Approach 1: Sieve of Eratosthenes (Optimal)
1. Create a boolean array `isPrime` of size n, initialized to true
2. Mark 0 and 1 as non-prime (false)
3. For each number i from 2 to sqrt(n):
- If i is prime, mark all multiples of i as non-prime
4. Count all true values in the array
Approach 2: Trial Division
1. For each number from 2 to n-1, check if it's prime
2. To check if a number is prime, try dividing by all numbers from 2 to sqrt(n)
3. Count the prime numbers found
Approach 3: Optimized Trial Division
1. Only check odd numbers (except 2)
2. Only check divisibility up to sqrt(n)
3. Use early termination if a divisor is found
Dry Run
Let's trace through Example 1: n = 10
Sieve of Eratosthenes:
- Initialize: [true, true, true, true, true, true, true, true, true, true]
- Mark 0,1: [false, false, true, true, true, true, true, true, true, true]
- i=2: Mark multiples of 2: [false, false, true, true, false, true, false, true, false, true]
- i=3: Mark multiples of 3: [false, false, true, true, false, true, false, true, false, false]
- Count primes: 4 (positions 2,3,5,7)
Trial Division:
- Check 2: prime ✓
- Check 3: prime ✓
- Check 4: not prime (divisible by 2)
- Check 5: prime ✓
- Check 6: not prime (divisible by 2)
- Check 7: prime ✓
- Check 8: not prime (divisible by 2)
- Check 9: not prime (divisible by 3)
- Total: 4 primes
Key Insights
1. Sieve Efficiency: Sieve of Eratosthenes is O(n log log n) time complexity
2. Square Root Optimization: Only need to check up to sqrt(n) for primality
3. Memory Trade-off: Sieve uses O(n) space but is much faster
4. Edge Cases: Handle n ≤ 2 carefully
Edge Cases
1. n = 0: Return 0
2. n = 1: Return 0
3. n = 2: Return 0 (no primes less than 2)
4. Large n: Consider memory constraints
Time and Space Complexity
- Time Complexity: O(n log log n) for Sieve, O(n√n) for trial division
- Space Complexity: O(n) for Sieve, O(1) for trial division