Напишите программу, которая вычислит .
– это арифметическая функция (функция Эйлера), значение которой равно количеству натуральных чисел, не превышающих n и взаимно простых с ним.
Нетрудно заметить, что 650933 простое число, а для простых чисел p, очевидно, функция Эйлера равна p — 1 (так как с p взаимнопросты все числа до него).
Ладно-ладно, шучу
if a == b:
return a
if a != 0 and b != 0:
return gcd(a % b, b % a)
else:
return a + b
def phi(n):
fi = 0
for i in range(1, n + 1):
if gcd(n, i) == 1:
fi += 1
return fi
print(phi(650933))