Home > Algorithm > Thuật toán Euclid tìm ước chung lớn nhất của 2 số

Thuật toán Euclid tìm ước chung lớn nhất của 2 số

1.Giới thiệu
Thuật toán Euclid tìm ước chung lớn nhất của 2 số dựa trên nguyên lý sau:

Nếu p>q thì UCLN(p,q) = UCLN(r,q) với r = p%q

2.Cài đặt trong Java

public static int gcd(int p, int q) {
   if (q == 0) {
      return p;
   }
   return gcd(q, p % q);
}
Advertisements
Categories: Algorithm
  1. No comments yet.
  1. No trackbacks yet.

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

%d bloggers like this: