Hide

Problem H
Prime Count

Given a positive integer $N$, compute the number of primes less than $N$.

Input

The first line contains the integer $N$ ($1 \le N \le 10^{11}$).

Output

Print the number of primes less than $N$.

Scoring

Your solution will be tested on a set of test groups, each worth a number of points. To get the points for a test group you need to solve all test cases in the test group.

Group

Points

Constraints

$1$

$1$

$N \le 10^6$

$2$

$1$

$N \le 10^7$

$3$

$1$

$N \le 3 \cdot 10^7$

$4$

$1$

$N \le 10^8$

$5$

$1$

$N \le 2 \cdot 10^8$

$6$

$1$

$N \le 10^{9}$

$7$

$1$

$N \le 10^{10}$

$8$

$1$

$N \le 10^{11}$

Sample Input 1 Sample Output 1
10
4

Please log in to submit a solution to this problem

Log in