Bilangan bulat terbesar yang dapat dengan sempurna membagi dua bilangan bulat dikenal sebagai GCD atau HCF dari kedua angka tersebut.


Contoh 1: Temukan GCD menggunakan while loop

#include 
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 << "HCF = " << n1;
    return 0;
}

Keluaran

Enter two numbers: 78
52
HCF = 26

Dalam program di atas, angka yang lebih kecil dikurangkan dari angka yang lebih besar dan angka itu disimpan di tempat angka yang lebih besar.

Proses ini berlanjut sampai, dua angka menjadi sama yaitu HCF.


Contoh: 2. Temukan HCF / GCD menggunakan untuk loop

#include 
using namespace std;

int main() {
    int n1, n2, hcf;
    cout << "Enter two numbers: ";
    cin >> n1 >> n2;

    // Swapping variables n1 and n2 if n2 is greater than n1.
    if ( n2 > n1) {   
        int temp = n2;
        n2 = n1;
        n1 = temp;
    }
    
    for (int i = 1; i <=  n2; ++i) {
        if (n1 % i == 0 && n2 % i ==0) {
            hcf = i;
        }
    }

    cout << "HCF = " << hcf;
    return 0;
}

Logika program ini sederhana.

Dalam program ini, bilangan bulat kecil antara n1 dan n2 disimpan di n2. Kemudian loop diulang dari i = 1 untuk i <= n2 dan di setiap iterasi, nilai saya bertambah 1.

Jika kedua angka dapat dibagi saya kemudian, nomor itu disimpan dalam variabel hcf.

Ketika iterasi selesai, HCF akan disimpan dalam variabel hcf.