eolymp
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