Вычислить функцию Эйлера от чисел 567 и 1280

Функция Эйлера φ(n), где n ∈ N — количество числел, меньших n и взаимно простых с n. Считать φ(1) = 1.

Можно проверять все m < n на взаимную простоту с n. Но при больших n вычисления могут занять слишком много времени.

Простое число всегда взаимно просто со всеми числами меньше себя. Таким образом для простых n: φ(n) = n - 1

Это частный случай для φ(p^k) = p^k - p^{k - 1} при k = 1. То есть у n единственный простой делитель, который повторен k раз.

Если некоторые p и q взаимно просты, то pq будет взаимно просто со всеми числами, меньшими себя, кроме тех, которые кратны хотя бы одному делителю p или хотя бы одному делителю q: φ(pq) = φ(p)φ(q).

Разложим n на простые множители и запишем в каноническом виде: n = p₁^a₁ p₂^a₂ ... p_k^a_k, где p_i — различные простые числа, тогда φ(n) = (p₁^a₁ - p₁^{a₁ - 1}) (p₂^a₁ - p₂^{a₂ - 1}) ... (p_k^a_k - p_k^{a_k - 1}).

567 = 3⁴⋅7, φ(567) = φ(3⁴⋅7) = φ(3⁴)⋅φ(7) = 54⋅6 = 324

1280 = 2⁸⋅5, φ(1280) = φ(2⁸⋅5) = φ(2⁸)⋅φ(5) = 128⋅4 = 512

математика