[C++] Tìm UCLN, BCNN của hai số bất kì

[C++] Tìm UCLN, BCNN của hai số bất kì

$\boxed{\text{BÀI TOÁN}}$ Nhập từ bàn phím $m,n$ ($m,n \geq 10^{6}$). In ra màn hình BCNN, UCLN của hai số m,n?

$\boxed{\text{THUẬT TOÁN}}$ Với cách tìm BCNN thì ta chỉ cần chia tích $m.n$ cho UCLN. 

Để tìm UCLN thì có nhiều cách tìm:

C1: Duyệt i từ n đến 1 nếu như m và n đều chia hết cho i thì break và i là UCLN

(Chú ý: Chạy từ n đến 1)

C2: Dùng thuật toán: UCLN(m,n)=UCLN(n,m-n)=...... Ta sẽ dùng vòng lặp while cho nó!

C3: Thuật toán Euclid (Tối ưu nhất) UCLN(m,n)=UCLN(n,r) (r = m mod n)

Qua 3 cách trên thì mình chỉ trình bày cách tối ưu nhất, những cách khác bạn có thể tham khảo tại diễn đàn của nhóm tại đây:

$\boxed{\text{BÀI LÀM}}$

#include <iostream>

#include <math.h>

using namespace std;

int main()

{

    long long m,n,tg,s;

    cout<<"Nhap m,n: ";cin>>m>>n;s=m*n;

    if (m<n) {tg=m;m=n;n=tg;}

    while (n!=0)

    {tg=m %n;m=n;n=tg;}

    cout<<"UCLN la: "<<m<<", BCNN la: "<<s/m;

    return 0;

}