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

Вот несколько методов расчета функции Эйлера от 1 до n, а также примеры кода:

1. Наивный подход.
   Наивный подход предполагает проверку каждого числа от 1 до n по отдельности, чтобы определить, является ли оно взаимно простым с n. Следующий код Python демонстрирует этот метод:

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

2. Подход с простой факторизацией:
   Этот подход использует простую факторизацию n для эффективного вычисления общей функции Эйлера. В примере кода ниже показан этот метод:

def euler_totient_prime_factors(n):
    result = n  # Initialize result as n
    # Find all prime factors of 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

3. Подход сита.
   Этот подход использует алгоритм «Решето Эратосфена» для эффективного расчета функции Эйлера. Следующий код демонстрирует этот метод:

def euler_totient_sieve(n):
    phi = [i for i in range(n + 1)]
    for p in range(2, n + 1):
        if phi[p] == p:  # p is a prime number
            phi[p] = p - 1
            for i in range(2 * p, n + 1, p):
                phi[i] = (phi[i] // p) * (p - 1)
    return phi