Дано натуральное число
\(n <= 10^9,\) определите количество натуральных чисел, меньших
\(n\) и взаимно простых с
\(n\). Это число обозначается
\( f(n) \)и называется фи-функцией Эйлера. Сложность алгоритма должна быть
\( O(\sqrt{n})\) .
Входные данные
На вход подается натуральное число
n.
Выходные данные
Выведите ответ на задачу.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
2 |
1 |