3

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

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

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

ввод
10
вывод
4

1
  • Ну, есть тупой способ - перебором :) Для небольших n вполне годится. Для больших я бы находил простые делители n, дальше методом включения-исключения искал бы количество не взаимно простых и вычитал бы из n...Написать не могу - не настолько хорошо знаю Python :(
    – Harry
    Commented 11 июн. 2020 в 5:34

3 ответа 3

7

Ну, есть тупой способ - перебором :) Для небольших 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())));
0

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

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

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

Ваш ответ

Нажимая «Отправить ответ», вы соглашаетесь с условиями пользования и подтверждаете, что прочитали политику конфиденциальности.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.