Skills101
← All coding problems

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).

Loading editor…

Log in to run and submit your code — it's free.