Count Primes
easySave
MathNumber Theory
Given a positive integer n, count the number of prime numbers less than n. A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself.
Example 1
Input
[ 10 ]
Output
4
Explanation. There are four prime numbers less than 10: 2, 3, 5, and 7.
Example 2
Input
[ 0 ]
Output
0
Explanation. There are no prime numbers less than 0.
Example 3
Input
[ 1 ]
Output
0
Explanation. There are no prime numbers less than 1.
Example 4
Input
[ 2 ]
Output
0
Explanation. The prime number must be greater than 1. Therefore, there are no primes less than 2.
Example 5
Input
[ 100 ]
Output
25
Explanation. The number of prime numbers less than 100 is 25.
Follow-up: Can you implement an optimized version of the algorithm to find primes more efficiently, perhaps using the **Sieve of Eratosthenes** method?
Constraints:
1 <= n <= 10^6. Input will always be a positive integer.
- Views
- 3