Упорядоченные дроби 3

На уроке информатики Алексей решил задачу №422 «Упорядоченные дроби» с сайта «Школа программиста».

Алексей задумался: а сколько всего несократимых дробей между 0 и 1 включительно, знаменатели которых не превышают N?

Помогите ему в этом!

Входные данные

Входной файл INPUT.TXT содержит натуральное число N (1 ≤ N ≤ 10⁸).

Выходные данные

В выходной файл OUTPUT.TXT выведите ответ на задачу.

Пример

Пояснение

В примере при N = 4 мы получаем 7 дробей: $\frac{0}{1},\frac{1}{4},\frac{1}{3},\frac{1}{2},\frac{2}{3},\frac{3}{4},\frac{1}{1}.$

Автор задачи

Владимир Игоревич Лукьянчиков

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]