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 * 106The key challenge in Count Primes is determining how many prime numbers exist strictly less than a given integer n. A naive strategy would test each number individually for primality, but this quickly becomes inefficient for large values of n. Instead, an optimized approach uses the Sieve of Eratosthenes.
The idea behind the sieve is to iteratively mark multiples of each prime number starting from 2. You maintain an array of boolean flags representing whether each number is potentially prime. Beginning with the smallest prime, you mark all of its multiples as non-prime. Repeating this process ensures that every composite number gets eliminated early.
This method avoids repeated divisibility checks and significantly improves performance. The algorithm runs in approximately O(n log log n) time with O(n) space, making it one of the most efficient and widely used approaches for prime counting problems in interview settings.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Sieve of Eratosthenes | O(n log log n) | O(n) |
| Naive primality check for each number | O(n√n) | O(1) |
take U forward
Use these hints if you're stuck. Try solving on your own first.
Checking all the integers in the range [1, n - 1] is not efficient. Think about a better approach.
Since most of the numbers are not primes, we need a fast approach to exclude the non-prime integers.
Use Sieve of Eratosthenes.
The Sieve of Eratosthenes is a classic algorithm to find all prime numbers up to a given limit. It efficiently marks non-prime numbers in a boolean array, allowing us to count the prime numbers left unmarked.
It operates by marking the multiples of each prime starting from 2, the smallest prime. This optimization significantly reduces the number of operations needed compared to checking each number individually.
Time Complexity: O(n log log n)
Space Complexity: O(n)
1#include <stdio.h>
2#include <stdbool.h>
3
4int countPrimes(int n) {
5 if (n <= 2)
This implementation uses a boolean array to keep track of prime numbers. We initialize the array assuming all numbers are prime, then use the Sieve of Eratosthenes method to mark non-prime numbers. Finally, we count the number of prime numbers remaining unmarked up to n.
A more basic approach to this problem is to check each number individually for primality. This involves testing each number for factors up to its square root. While less efficient than the sieve, it provides an instructive example of brute force in algorithm design.
Time Complexity: O(n√n)
Space Complexity: O(1)
1using System;
2
public class Solution {
public bool IsPrime(int n) {
if (n <= 1) return false;
if (n <= 3) return true;
if (n % 2 == 0 || n % 3 == 0) return false;
for (int i = 5; i * i <= n; i += 6) {
if (n % i == 0 || n % (i + 2) == 0) return false;
}
return true;
}
public int CountPrimes(int n) {
int count = 0;
for (int i = 2; i < n; i++) {
if (IsPrime(i)) count++;
}
return count;
}
public static void Main() {
Solution sol = new Solution();
Console.WriteLine(sol.CountPrimes(10)); // Output: 4
}
}
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, variations of prime counting and the Sieve of Eratosthenes are common interview topics at major tech companies. They test understanding of number theory concepts, array manipulation, and algorithmic optimization.
The optimal approach is the Sieve of Eratosthenes. It works by iteratively marking multiples of each prime number starting from 2, eliminating composite numbers efficiently. This method runs in O(n log log n) time and is significantly faster than checking each number individually.
Most implementations use a boolean array or list to track whether each number is prime. The array initially assumes all numbers are prime, and multiples of discovered primes are marked as false during the sieve process.
The sieve avoids repeated divisibility checks by eliminating composite numbers in bulk. Once a prime is found, all of its multiples are marked in one pass, which reduces unnecessary computations and improves performance.
The C# version uses a similar naive strategy by checking divisibility up to the square root for each number. This method entails iterating through numbers sequentially and assessing their factors.