Вы когда-нибудь сталкивались с математической функцией, которая выглядела так, будто она взята прямо из книги заклинаний волшебника? Что ж, функция Тотиента Эйлера — одна из таких очаровательных концепций! В этой статье мы рассмотрим эту замечательную функцию, раскроем ее внутреннюю работу и предоставим вам несколько методов для ее реализации в вашем коде. Итак, пристегните ремни и приготовьтесь раскрыть магию функции Тотиент Эйлера!

Что такое функция тотента Эйлера?
Функция тотиента Эйлера, обозначаемая как φ(n), представляет собой математическую функцию, которая подсчитывает количество натуральных чисел, взаимно простых с заданным положительным целым числом n. Другими словами, он вычисляет количество целых чисел от 1 до n, которые не имеют общих делителей с n (кроме 1).

Метод 1: подход грубой силы
Давайте начнем с простого, хотя и менее эффективного подхода. Мы можем перебрать все числа от 1 до n и проверить, взаимно ли они просты с n, используя алгоритм Евклида. Вот реализация Python:

def euler_totient_brute_force(n):
    count = 0
    for i in range(1, n+1):
        if math.gcd(i, n) == 1:
            count += 1
    return count

Метод 2: факторизация простых чисел
Другой метод расчета функции тотента Эйлера — использование факторизации простых чисел. Мы можем выразить n как произведение его простых множителей и использовать формулу:

φ(n) = n (1 – 1/p1)(1 – 1/p2) …(1 – 1/pk)

где p1, p2, …, pk — отдельные простые делители числа n. Вот пример кода:

def euler_totient_prime_factorization(n):
    result = n
    for p in range(2, int(math.sqrt(n)) + 1):
        if n % p == 0:
            while n % p == 0:
                n //= p
            result *= (1.0 - (1.0 / p))
    if n > 1:
        result *= (1.0 - (1.0 / n))
    return int(result)

Метод 3: формула произведения Эйлера
Формула произведения Эйлера — еще один элегантный метод вычисления φ(n). Он использует тот факт, что φ(n) является мультипликативной функцией, а это означает, что φ(m n) = φ(m)φ(n), если m и n взаимно просты. Вот реализация Python:

def euler_totient_product_formula(n):
    result = n
    p = 2
    while p * p <= n:
        if n % p == 0:
            while n % p == 0:
                n //= p
            result -= result // p
        p += 1
    if n > 1:
        result -= result // n
    return result

Функция тотиента Эйлера — мощный инструмент в теории чисел, который позволяет нам подсчитать количество взаимно простых целых чисел с заданным числом. В этой статье мы исследовали три различных метода расчета φ(n): метод грубой силы, факторизацию простых чисел и формулу произведения Эйлера. Каждый метод имеет свои преимущества и варианты использования, поэтому выберите тот, который лучше всего соответствует вашим потребностям. Теперь, когда в вашем распоряжении есть эти методы, раскройте магию функции Тотиент Эйлера в своем собственном коде!