Tìm ước số chung lớn nhất của 2 số

Ước số chung lớn nhất là gì?

 Trong toán học, nếu số nguyên a chia hết cho số nguyên b thì số b được gọi là ước của số nguyên a, a được gọi là bội của b. Số nguyên dương b lớn nhất là ước của cả hai số nguyên a, b được gọi là ước số chung lớn nhất (ƯCLN) của a và b.

Trong trường hợp cả hai số nguyên a và b đều bằng 0 thì chúng không có USCLN vì khi đó mọi số tự nhiên khác không đều là ước chung của a và b. Nếu chỉ một trong hai số a hoặc b bằng 0, số kia khác 0 thì USCLN của chúng bằng giá trị tuyệt đối của số khác 0.

Ký hiệu ước số chung lớn nhất.

Ước chung lớn nhất của a và b được ký hiệu là ƯCLN(a, b), hay đơn giản hơn là (a, b). Hai số nguyên tố cùng nhau nếu ước chung lớn nhất của chúng bằng 1.

Ví dụ ước chung lơn nhất.

ƯCLN(42, 56)=14, do đó, 42 = 3x14 và 56 = 4x14 vậy USCLN(42,56) = 14

Ước số chung lớn nhất trong lập trình

Để tìm ước số chung lớn nhất của 2 số nguyên trong các ngôn ngữ lập trình,
ta có thể tìm được bằng việc phân tích hai số đó ra thừa số nguyên tố, ví dụ như sau :
USCLN(18,84) ta phân tích như sau :
18 = 2·3 mũ 2
84 = 2 mũ 2·3·7
Nếu chúng ta dùng phương pháp này để phần tích ra các số nhỏ thì việc mất thời gian là khá nhiều, dẫn tới phức tạp. Nên vì thế người ta dùng giải thuật Euclid để phân tích ra USCLN

Dưới đây là code tìm ước số chung lớn nhất (USCLN) bằng java.

Đầu tiên ta viết một hàm tìm ước số chung lớn nhất

int USCLN(int a, int b){
a = Math.abs(a);
b = Math.abs(b);
if(a == 0 || b == 0){
return a+b;
}
while(a != b){
if(a >b){
a = a- b;
}else{
b = b -a;
}
}
return a;
}

Giải thích :
a = Math.abs(a),b = Math.abs(b) dùng để lấy giá trị tuyết đối của 2 số a và bằng
nếu a == 0  hoăc b == 0  thì ước số chung lớn nhất a+b;
Ở vòng lặp white khi a != b thì vòng lặp thực hiện câu lệnh ở phía trong.

Chúng ta khai báo hàm Main như sau:

public static void main(String []args){
USCLN uscln = new USCLN();
System.out.println("Tim uoc so chung lon nhat");
System.out.print("USCLN(18,84) = " + uscln.USCLN(18, 84));
}

Toàn bộ code tìm USCLN của 2 số như sau :

package baitap1;
public class USCLN {
int USCLN(int a, int b){
a = Math.abs(a);
b = Math.abs(b);
if(a == 0 || b == 0){
return a+b;
}
while(a != b){
if(a >b){
a = a- b;
}else{
b = b -a;
}
}
return a;
}
public static void main(String []args){
USCLN uscln = new USCLN();
System.out.println("Tim uoc so chung lon nhat");
System.out.print("USCLN(18,84) = " + uscln.USCLN(18, 84));
}
}