Count Primes up to N
easyMath & Number Theory+10 XPTime limit 2s
A school maths club wants to know how many prime numbers there are from 1 to n. A prime is a number greater than 1 whose only divisors are 1 and itself (2, 3, 5, 7, 11, …).
Input: one integer n.
Output: how many primes are less than or equal to n.
Constraints: 0 ≤ n ≤ 5·10⁶.
Think about it: checking every number one by one is too slow for the largest n. Use the Sieve of Eratosthenes: start with every number marked prime, and for each prime p (starting from 2) cross out p·p, p·p + p, p·p + 2p, …. What stays unmarked is prime.
Sample input 1
10
Sample output 1
4
Sample input 2
2
Sample output 2
1
Read input from standard input and print the answer to standard output. Your code runs in a secure sandbox against the samples (Run) and hidden tests (Submit).