Функция Эйлера
(Время: 1 сек. Память: 16 Мб Сложность: 57%)
Функция Эйлера φ(n) – функция, равная количеству натуральных чисел, не превосходящих ее аргумента n и взаимно простых с n.
Требуется по заданному натуральному числу n вычислить значение функции Эйлера, т.е. найти количество таких натуральных чисел m, что m ≤ n и НОД(m,n)=1.
Входные данные
Входной файл INPUT.TXT содержит натуральное число n (n ≤ 109).
Выходные данные
В выходной файл OUTPUT.TXT выведите φ(n).
Примеры
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 1 | 1 |
| 2 | 567 | 324 |
| 3 | 1280 | 512 |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| 
