Kiến thức

Tìm ước số chung lớn nhất của 2 số-Thủ thuật lập trình

Bạn đang xem: Tìm ước số chung lớn nhất của 2 số-Thủ thuật lập trình

Ướ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.

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

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 = 3×14 và 56 = 4×14 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));
}
}

Read more

Chuyên mục: Kiến thức

Related Articles

Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *

Check Also
Close
Back to top button