Problem Statement
Count the number of prime numbers less than a non-negative integer n.
Example
-
Input: n = 10
Output: 4
Explanation: The prime numbers less than 10 are 2, 3, 5, 7.
-
Input: n = 20
Output: 8
Explanation: The prime numbers less than 20 are 2, 3, 5, 7, 11, 13, 17, 19.
Brute Force Approach
Approach
Idea: For each number less than n, check if it is prime by testing divisibility by all numbers up to its square root.
Steps
- Initialize a counter to
0.
- Loop through each number from
2 to n - 1.
- For each number, check if it is divisible by any integer from
2 to the square root of the number.
- If it is not divisible, it is a prime number; increment the counter.
- Return the counter.
Time & Space Complexity
- Time Complexity: O(n√n)
- For each number, we check divisibility up to its square root.
- Space Complexity: O(1)
- Only a few variables are used.
Code Snippet
Dry Run
Input: n = 10
- Loop through numbers
2 to 9:
2: Prime, increment count = 1.3: Prime, increment count = 2.4: Not prime.5: Prime, increment count = 3.6: Not prime.7: Prime, increment count = 4.8: Not prime.9: Not prime.
- Return
4.
Efficient Approach
Approach
Idea: Use a boolean array to mark non-prime numbers. Start with the assumption that all numbers are prime and mark multiples of each prime number as non-prime.
Steps
- Create an array
isPrime of size n and initialize all values to true. Set isPrime[0] and isPrime[1] to false (0 and 1 are not prime).
- Loop through numbers from
2 to n - 1:
- If the number is marked as prime, count it.
- Mark all multiples of the number as non-prime.
- Return the count of
true values in the array.
Time & Space Complexity
- Time Complexity: O(log log n)
- Each number checks all its multiples.
- Space Complexity: O(n)
- An array of size
n is used.
Code Snippet
Dry Run
Input: n = 10
- Initialize
isPrime as [false, false, true, true, true, true, true, true, true, true].
- Loop through numbers
2 to 9:
2: Prime, increment count = 1, mark multiples: [false, false, true, true, false, true, false, true, false, true].3: Prime, increment count = 2, mark multiples: [false, false, true, true, false, true, false, true, false, false].4: Not prime.5: Prime, increment count = 3.6: Not prime.7: Prime, increment count = 4.8: Not prime.9: Not prime.
- Return
4.
Complexity Analysis
| Operation | Brute Force | Efficient Approach |
|---|
| Time Complexity | O(n√n) | O(log log n) |
| Space Complexity | O(1) | O(n) |
Note: The time complexity of the efficient approach is based on the assumption that the number of primes less than n is approximately n / log(n). This is a result of the Prime Number Theorem. This is also known as the Sieve of Eratosthenes.
Conclusion
- The brute force approach is simple but inefficient for large values of
n due to its O(n√n) time complexity.
- The efficient approach reduces redundant checks by marking multiples of prime numbers, achieving better scalability.
- This problem demonstrates the importance of using optimized data structures like boolean arrays for problem-solving.