Функция тотента Эйлера, также известная как фи-функция Эйлера, представляет собой математическую функцию, которая подсчитывает количество натуральных чисел, меньших или равных заданному числу n, которые взаимно просты (относительно простые) с n. Другими словами, он подсчитывает количество чисел, у которых нет общих делителей с n, кроме 1.
Существует несколько методов вычисления функции Эйлера:
-
Метод простой факторизации: если n можно представить в виде произведения различных простых чисел, скажем, n = p1^a1 p2^a2… pk^ak, тогда значение функции Эйлера можно вычислить по формуле: φ(n) = n(1 – 1/p1) (1 – 1/p2)… * (1 – 1/уп).
-
Метод Sieve. Этот метод включает в себя создание массива размера n и инициализацию всех элементов по их соответствующим индексам. Затем алгоритм перебирает массив, помечая кратные каждому простому числу как невзаимнопростые. Остальные неотмеченные числа взаимно просты с n, и подсчет этих чисел дает значение φ(n).
-
Мультипликативное свойство: если n и m — взаимно простые положительные целые числа, то φ(nm) = φ(n) * φ(m). Это свойство можно использовать для расчета значения φ(n) путем разложения n на простые коэффициенты и вычисления φ для каждого фактора.
-
Рекурсивный метод: функция Эйлера имеет рекурсивное определение, где φ(n) задается суммой φ(d) для всех положительных делителей d числа n. Этот метод можно использовать для вычисления φ(n) путем рекурсивного вычисления φ для меньших делителей до тех пор, пока не будет достигнут базовый случай φ(1).
-
Таблица функций Totient: для небольших значений n можно использовать предварительно вычисленную таблицу значений φ(n) для прямого поиска значения φ(n) без выполнения каких-либо вычислений.