Euler's Totient Function – Thuật Toán Tính Phi Hàm Euler | Nhan Nguyen

Trang chủ » Hàm Phi Euler C++ » Euler's Totient Function – Thuật Toán Tính Phi Hàm Euler | Nhan Nguyen

Có thể bạn quan tâm

Skip to content HomeEuler’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

Chia sẻ:

  • X
  • Facebook
Like Loading... Post navigation ← Địa chỉ Logic và địa chỉ Vật lý Pillai’s arithmetical function – Thuật toán tính hàm Pillai →

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

  1. […] Theo tính chất của hàm gcd, nếu ta có thì . Do đó công thức của hàm Pillai sẽ là: , với là Hàm phi Euler […]

    LikeLike

    Reply

Leave a comment Cancel reply

Δ

Search for: Recent Posts
  • Print matrix in spiral order
  • Explain Normal Equation matrix formula
  • Sự khác nhau giữa Population và Sample
  • Thuật toán Kruskal tìm cây khung nhỏ nhì
  • UVa 1208 – Oreon
Archives
  • June 2017
  • April 2017
  • March 2017
  • February 2017
  • December 2016
  • November 2016
  • October 2016
  • September 2016
  • August 2016
  • July 2016
  • March 2016
  • February 2016
  • January 2016
  • December 2015
  • November 2015
  • October 2015
  • September 2015
  • August 2015
  • July 2015
  • May 2015
Recent Comments
nhannguyen95's avatarnhannguyen95 on Bài tập Ngôn ngữ hình thức kèm…
Ks's avatarKs on Bài tập Ngôn ngữ hình thức kèm…
Beby's avatarBeby on [SPOJ] QBGAME – Trò chơi…
Uyen Pham's avatarUyen Pham on Đại từ trong tiếng Pháp…
Tín's avatarTín on Bài tập Ngôn ngữ hình thức kèm…
My studio fb
My studio fb
Privacy & Cookies: This site uses cookies. By continuing to use this website, you agree to their use. To find out more, including how to control cookies, see here: Cookie Policy
  • Comment
  • Reblog
  • Subscribe Subscribed
    • Nhan Nguyen
      • Sign me up
    • Already have a WordPress.com account? Log in now.
    • Nhan Nguyen
    • Subscribe Subscribed
    • Sign up
    • Log in
    • Copy shortlink
    • Report this content
    • View post in Reader
    • Manage subscriptions
    • Collapse this bar
%d Design a site like this with WordPress.comGet started

Từ khóa » Hàm Phi Euler C++