Tìm UCLN Và BCNN (Euclid) trong C++

1. UCLN: 

• Để tìm UCLN của hai sô a và b, ví dụ UCLN(6,9) thì ta tìm các ước của 6 và các ước của 9.
• Các ước của 6 : lấy kết quả chia hết của  (6 chia cho từ 1 đến 6) ta có bảng kết quả sau:
  

  Các ước của 6

  1

  2

  3

  6

• Các ước của 9 : lấy kết quả chia hết của  (9 chia cho từ 1 đến 9) ta có bảng kết quả sau:
  

  Các ước của 9

  1

  3

  9

• Vậy UC(6,9) ={ 1,3}  ⇒ UCLN(6, 9) = {3}

2 . BCNN: 

• • Để tìm BCNN của hai sô a và b, ví dụ BCNN(6,9) thì ta làm như sau:
  • B(6) = {6, 12, 18, 24, …}
  • B(9) = {9, 18, 27,…}
  • BCNN(6,9)={18}. Vậy kết luận số x ∈ (a,b) nếu x  \vdots  a và x  \vdots  b.
  • Thuật toán Euclid
  • Nếu a chia hết cho b ( a%b =0 ) thì UCLN(a,b) là b.
  • Nếu a chia hết cho b dư r ( r = a % b) thì UCLN(a,b)  = UCLN(b,r) 
  • BCNN = (a*b) / UCLN
  • Sơ đồ mô tả thuật toán:
  • Code C++

 
#include <bits/stdc++.h>
using namespace std;
long long int a, b, r, ucln, bcnn, ta, tb;
int main ()
{
cin >> a >> b;
ta = a;
tb = b;
while(b != 0){
r = a % b;
{
	if (r == 0){
	ucln = b;
	break;
	}
	else {
		a = b ;
		b = r;
	}
}
}
bcnn = (ta*tb)/ucln;
cout << "UCLN:"<< " " << ucln << endl;
cout << "BCNN:" << " " << bcnn;
return 0;
}

– Kết quả :

• • Ngoài ra để tìm  UCLN và BCNN sử dụng hàm có sẵn của C++ :
  • Code C++:

 
#include <bits/stdc++.h>
using namespace std;

int main() {
    long long int a,b;
    cin>>a>>b;
    cout << "UCLN:" <<" "<< __gcd(a, b) << endl;
    cout << "BCNN:" <<" "<< (a*b)/__gcd(a, b);

}