Hàm Phi Euler \(\varphi(N)\) tính số lượng số nguyên từ \(1\) đến \(N\) nguyên tố cùng nhau với \(N\).

Công thức phân tích thừa số nguyên tố của \(N\): \(N = p_1^{k_1} \cdot p_2^{k_2} \dots p_m^{k_m}\)

Thì giá trị hàm phi Euler là: \(\varphi(N) = N \cdot \left(1 - \frac{1}{p_1}\right) \cdot \left(1 - \frac{1}{p_2}\right) \dots \left(1 - \frac{1}{p_m}\right)\)

Thuật toán: Ta phân tích thừa số nguyên tố của \(N\) bằng thuật toán độ phức tạp \(O(\sqrt{N})\):

1. Duyệt các số nguyên \(i\) từ \(2\) đến \(\sqrt{N}\).
2. Nếu \(i\) là ước của \(N\), ta nhân \(\varphi(N)\) với \(\left(1 - \frac{1}{i}\right)\) (tương đương chia cho \(i\) rồi nhân với \(i - 1\)), sau đó chia \(N\) cho \(i\) đến khi không chia hết nữa.
3. Nếu sau khi duyệt xong mà \(N > 1\), tức là \(N\) hiện tại là một số nguyên tố, ta thực hiện bước cập nhật cuối cùng cho số nguyên tố này. ## Mã nguồn C++ tham khảo ```cpp #include <iostream>

using namespace std;

long long phi(long long n) { long long ans = n; for (long long p = 2; p * p <= n; ++p) { if (n % p == 0) { while (n % p == 0) n /= p; ans -= ans / p; } } if (n > 1) ans -= ans / n; return ans; }

int main() { ios_base::sync_with_stdio(false); cin.tie(NULL);

long long n;
if (cin >> n) {
    cout << phi(n) << "\n";
}
return 0;

} ```