Question

C++ СИРИУС Функция Эйлера Дано натуральное число n, определите количество натуральных чисел, меньших n и взаимно простых с n.

Входные данные
Дано натуральное число n≤10^9.

Выходные данные
Выведите φ(n).

Ввод
10

Вывод
4

Answer 1

Если задача не на алгоритмы, то можно воспользоваться модулем math и методом gcd - наибольший общий делитель. Если наибольший общий делитель для числа в последовательности и общего количества натуральных чисел равен 1, то кладем его в список. После чего возвращаем длину этого списка

import math

def phi(n):

result = [i for i in range(1, n + 1) if math.gcd(n, i) == 1]

return len(result)

print(phi(10))

# OUT

# 4