Функция Эйлера и взаимно простые числа

Question

Функция Эйлера
Дано натуральное число n, определите количество натуральных чисел, меньших n и взаимно простых с n. Входные данные Дано натуральное число n≤10⁹.

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

ввод 10 вывод 4 Никак не пойму, как решать эту задачу!

Answer 1

Вот, я даже на 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())));

Answer 2

Если задача не на алгоритмы, то можно воспользоваться модулем 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

Answer 3

Другое оформление способа со списком без, собственно, самого списка и с не библиотечным вычислением НОД методом Евклида, вдруг кому пригодится

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))'

БЛОГ НА HUSL

Функция Эйлера и взаимно простые числа

Ответы (3 шт):