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 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.
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.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n log log n)
Space Complexity: O(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.
This solution implements a naive primality test, evaluating the primality of each number up to n. For each number, divisibility is tested up to the square root to determine if it is prime. Though simple, this method is not optimized for large input values.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n√n)
Space Complexity: O(1)
| Approach | Complexity |
|---|---|
| Sieve of Eratosthenes | Time Complexity: O(n log log n) |
| Naive Primality Test | Time Complexity: O(n√n) |
L6. Sieve of Eratosthenes | Maths Playlist • take U forward • 99,332 views views
Watch 9 more video solutions →Practice Count Primes with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor