Олимпиадный тренинг

Задача 33687. Функция Эйлера


Задача

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

Входные данные
На вход подается натуральное число n.

Выходные данные
Выведите ответ на задачу.
 

 

Примеры
Входные данные Выходные данные
1 2 1