Функция Эйлера (Euler's totient function)
Для заданного числа n требуется вычислить результат функции Эйлера.
Функция Эйлера определяет количество целых чисел от 1 до n, которые взаимно просты с n. Другими словами, это все числа, у которых наибольший общий делитель с n равен 1.
Входные данные
Вход содержит одно целое число n (1 ≤ n ≤ ).
Выходные данные
Программа должна вывести результат вычисления функции Эйлера для n.
Примеры
Input | Output |
|---|---|
20 | 8 |
9 | 6 |
Пояснение
20 → 1, 3, 7, 9, 11, 13, 17, 19
9 → 1, 2, 4, 5, 7
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB