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.