Wednesday, January 15, 2020

Tìm ước số chung lớn nhất trong C++

Theo wikipedia Trong toán học, ước số chung lớn nhất (ƯSCLN) hay ước chung lớn nhất (ƯCLN) của hai hay nhiều số nguyên là số nguyên dương lớn nhất là ước số chung của các số đó.
Để hiểu ví dụ này, bạn nên có kiến thức về các chủ đề lập trình C ++ sau đây:
Tìm ước số chung lớn nhất trong C++

Ví dụ, ước chung lớn nhất của 6 và 15 là 3 vì {\displaystyle 6:3=2}{\displaystyle 6:3=2} và {\displaystyle 15:3=5}{\displaystyle 15:3=5}.

Tổng quan về ướ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), tiếng Anh ký hiệu là gcd(a,b).
Hai số được gọi là số nguyên tố cùng nhau nếu ước chung lớn nhất của chúng bằng 1. Chẳng hạn, 9 và 28 là hai số nguyên tố cùng nhau.
Ước chung lớn nhất được sử dụng để đưa một phân số về dạng phân số tối giản. Chẳng hạn, ƯCLN(42, 56)=14.
Các tính chất của ước số chung lơn nhất.

  • ƯCLN(a, b), khi a và b không bằng không cả hai, có thể được định nghĩa tương đương như số nguyên dương d nhỏ nhất có dạng d = a·p + b·q trong đó p và q là các số nguyên. Định lý này được gọi là đẳng thức Bézout. Các số p và q có thể tính nhờ Giải thuật Euclid mở rộng.
  • ƯCLN(a, 0) =|a|, với mọi a ≠ 0, vì mọi số khác không bất kỳ là ước của 0, và ước lớn nhất của a là|a|. Đây là trường hợp cơ sở trong thuật toán Euclid.

Sau đây là chương trình tìm ước số chung lơn nhất trong c++
#include <iostream>
using namespace std;
int main()
{
    int n1, n2;
    cout << "Enter two numbers: ";
    cin >> n1 >> n2;
   
    while(n1 != n2)
    {
        if(n1 > n2)
            n1 -= n2;
        else
            n2 -= n1;
    }
    cout << "USCLN = " << n1;
    return 0;
}
Kết quả của chương trình
Enter two numbers: 78
52
USCLN = 26