Теория чисел
Очень простая
Ограничение по времени выполнения 1 секунда
Ограничение по использованию памяти 128 мегабайт
Для заданного натурального числа n найдите количество таких чисел m, что 1 ≤ m ≤ n, НОД(m, n) ≠ 1 и НОД(m, n) ≠ m. Через НОД здесь обозначен "Наибольший Общий Делитель".
Входные данные
Каждая строка содержит одно натуральное число n (0 < n < 2^31).
Выходные данные
Для каждого значения n вывести в отдельной строке количество искомых чисел m.
Примеры
Ввод #1
Ответ #1
Отправки 2K
Коэффициент принятия 50 %