e-olymp
favorite We need a little bit of your help to keep things running, click on this banner to learn more
Competitions

Ukrainian Selection Camp to the European Girls' Olympiad in Informatics 2021

Знаменник

Знайдіть кількість правильних дробів, у яких знаменник не перевищує $n$. Дріб $\frac{a}{b}$ називається правильним, якщо \begin{enumerate} \item $a$, $b$~--- цілі додатні числа; \item $a \leq b$; \item найбільший спільний дільник $a$ та $b$~--- $1$. \end{enumerate} \InputFile Перший рядок містить одне ціле число $n$ ($1 \leq n \leq 10^6$). \OutputFile Виведіть одне ціле число~--- відповідь на задачу. \Scoring \begin{enumerate} \item ($30$ балів): $n \leq 10^3$; \item ($40$ балів): $n \leq 10^5$; \item ($30$ балів): без додаткових обмежень. \end{enumerate}
Time limit 1 second
Memory limit 256 MiB
Input example #1
5
Output example #1
10
Input example #2
10
Output example #2
32
Author Anton Tsypko