Войти
или
Зарегистрироваться
Курсы
Учебник
Экзамены
Олимпиады
Рубрикатор
Компилятор
Курсы
Арифметика
Функция Эйлера и другие задачи теории чисел
Модуль:
Функция Эйлера и другие задачи теории чисел
Задача
1
/9
Функция Эйлера
Теория
Нажмите, чтобы прочитать/скрыть
Функция Эйлера
Теорию можно почитать
здесь
.
Задача
Дано натуральное число
\(n <= 10^9,\)
определите количество натуральных чисел, меньших
\(n\)
и взаимно простых с
\(n\)
. Это число обозначается
\( f(n) \)
и называется фи-функцией Эйлера. Сложность алгоритма должна быть
\( O(\sqrt{n})\)
.
Входные данные
На вход подается натуральное число
n
.
Выходные данные
Выведите ответ на задачу.
Примеры
№
Входные данные
Выходные данные
1
2
1
1000
ms
256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач
Статистика успешных решений по компиляторам
Кол-во
С++ Mingw-w64
139
Free Pascal
1
Python
43
Комментарий учителя