Функция Эйлера - Функция Эйлера и другие задачи теории чисел

Task
Time limit: 1000 ms,
Memory limit: 256 Mb

Дано натуральное число

$n <= 10^9,$ определите количество натуральных чисел, меньших

$n$ и взаимно простых с

$n$ . Это число обозначается

$f(n)$ и называется фи-функцией Эйлера. Сложность алгоритма должна быть

$O(\sqrt{n})$ .

Примеры:

№	Входные данные	Выходные данные
1	2	1

Auto CHOOSE THE PROGRAMMING NECESSARY LANGUAGE!

Attach the program source file:
or enter the source code in the language:

​x
 
​

Results: