Функция Эйлера
Дано натуральное число n, определите количество натуральных чисел, меньших n и взаимно простых с n.
Входные данные
Дано натуральное число n≤109.
Выходные данные
Выведите φ(n).
ввод
10
вывод
4
Функция Эйлера
Дано натуральное число n, определите количество натуральных чисел, меньших n и взаимно простых с n.
Входные данные
Дано натуральное число n≤109.
Выходные данные
Выведите φ(n).
ввод
10
вывод
4
Ну, есть тупой способ - перебором :) Для небольших n вполне годится. Для больших я бы находил простые делители n, дальше методом включения-исключения искал бы количество не взаимно простых и вычитал бы из n...
Вот, я даже на Python ухитрился написать :)
def fi(n):
f = n;
if n%2 == 0:
while n%2 == 0:
n = n // 2;
f = f // 2;
i = 3
while i*i <= n:
if n%i == 0:
while n%i == 0:
n = n // i;
f = f // i;
f = f * (i-1);
i = i + 2;
if n > 1:
f = f // n;
f = f * (n-1);
return f;
print(fi(int(input())));
Если задача не на алгоритмы, то можно воспользоваться модулем 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
Другое оформление способа со списком без, собственно, самого списка и с не библиотечным вычислением НОД методом Евклида, вдруг кому пригодится
def Euclid(a, b): # функция Евклида
while a != 0 and b != 0:
if a > b:
a = a % b
else:
b = b % a
return max(a, b)
def EulerFunction_Euclid(n): # функция Эйлера через Евклида
result = 0
for i in range (1,n):
if Euclid(n,i) == 1:
result+=1
return result
n = int(input("Enter N"))
print(EulerFunction_Euclid(n))'