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 or equal to $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 |
