Функция Эйлера (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