Problem Description

Find the number of primes among $1, 2, \cdots, N$.

Input Format

One line containing an integer $N$.

Output Format

One line containing an integer, representing the number of primes.

10

4

Hint

For $40\%$ of the testdata, $1 \le N \le 10^6$.

For $80\%$ of the testdata, $1 \le N \le 10^7$.

For $100\%$ of the testdata, $1 \le N \le 10^8$.

Translated by ChatGPT 5