eolymp
Задачи

Степан и пары

Степан и пары

В последнее время Степан очень интересуется парами чисел, а кроме пар чисел его интересует наибольший общий делитель пары чисел, обозначим его как НОД(x, y). Сейчас у Степана есть целое число n и его интересует такая информация: сколько существует пар целых чисел (i, j), таких что 1i, jn и выполняется равенство i = НОД(i, j).

Помогите ему в решении нелёгкой задачи.

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

Одно целое число n (1n106).

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

Выывести количество искомых пар целых чисел.

Лимит времени 1 секунда
Лимит использования памяти 128 MiB
Входные данные #1
1
Выходные данные #1
1
Входные данные #2
4
Выходные данные #2
8
Входные данные #3
10
Выходные данные #3
27

Объяснение: В первом примере подходящей парой есть пара (1, 1), так как НОД(1, 1) = 1. Во втором примере подходят 8 пар чисел: (1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 4), (3, 3), (4, 4).

Источник III этап Всеукраинской олимпиады школьников 2012-2013, 1 тур