Count Primes up to N
Medium 40 XPMathArrays
Commonly asked at Amazon, Microsoft
Read n and print how many prime numbers are less than or equal to n. n can be up to 1,000,000, so testing each number one by one is too slow. Use the Sieve of Eratosthenes.
- Input
- One integer n.
- Output
- The count of primes ≤ n.
- Constraints
- 0 ≤ n ≤ 1,000,000
Sample 1
Input
10
Output
4
Explanation: 2, 3, 5, 7
Read input with input() (no prompt message) and print only the answer. Run tries the Input box; Submit checks all test cases.
Output Loading Python (first time takes a few seconds)
Press Run to see the result here.The solution unlocks after 3 submissions.