Euler’s totient function – Thuật toán tính Phi hàm Euler

Hàm số Euler của một số nguyên dương n (ký hiệu \phi(n)) là số các số i nguyên dương nhỏ hơn hoặc bằng n nguyên tố cùng nhau với n (GCD(i, n) = 1).

Một số công thức tính \phi(n):

  • \phi(n)=n\prod_{p|n}\left(1-\frac{1}{p}\right), với p là ước nguyên tố của n
  • \phi(n)=\sum_{d\mid n} d \cdot \mu(n/d), với d là ước của n và \mu là hàm Mobius

Công thức đầu tiên cho ta ý tưởng về cách tính Phi hàm Euler bằng sàng nguyên tố Sieve với độ phức tạp O(NlogN):
Code

Các nguồn tham khảo:

[1] https://vi.wikipedia.org/wiki/Phi_hàm_Euler

Happy coding

Advertisements

One thought on “Euler’s totient function – Thuật toán tính Phi hàm Euler

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s