Menghitung Faktor Persekutuan Terbesar Menggunakan Algoritma Euclid – Implementasi Dalam Bahasa C dan Pascal

Kali ini saya menulis tentang algoritma untuk menghitung greatest common divisor (GCD) atau faktor persekutuan terbesar (FPB) dari dua bilangan bulat. Algoritma yang akan dibahas di sini adalah Euclidean Algorithm atau Algoritma Euclid. Sesuai namanya, penemu algoritma ini memang Mbah Euclid tersebut, salah satu ahli matematika Yunani kuno.

Algoritma ini telah berusia cukup lama. Algoritma Euclid sudah ditulis sejak 3 abad sebelum masehi, dan sampai sekarang masih digunakan di dunia komputasi.

GCD atau FPB dari dua buah bilangan adalah suatu bilangan terbesar yang dapat membagi habis kedua bilangan tersebut (tanpa meninggalkan sisa). FPB biasanya dipelajari di matematika saat SD. Cara konvensionalnya biasanya adalah seperti pembahasan berikut.

Misalkan, ditanya: Berapa FPB dari 24 dan 30? Kalau zaman saya dulu, guru saya mengajarkan untuk menuliskan seluruh faktor yang ada dari kedua bilangan tersebut, kemudian mencari angka terbesar yang sama-sama dimiliki oleh kedua bilangan tersebut.

Faktor dari 24:
1, 2, 3, 4, [6], 8, 12 dan 24

Faktor dari 30:
1, 2, 3, 5, [6], 10, 15 dan 30

Seperti yang bisa pembaca lihat di atas, jadi berapa FPB dari 24 dan 30? Dari faktor yang telah diuraikan dari kedua bilangan tersebut, bilangan terbesar yang sama-sama dimiliki oleh kedua bilangan tersebut adalah 6. Berarti, 6 adalah FPB dari 24 dan 30.

Masalah di atas mungkin mudah diselesaikan jika angkanya relatif kecil, tetapi bagaimana kalau angkanya besar?

Kalau secara algoritmik, tentu akan sulit jika program yang dibuat harus mendata terlebih dahulu faktor-faktor dari masing-masing bilangan kemudian mencari angka terbesar yang sama-sama terdapat di daftar faktor dari kedua bilangan tersebut. Selain dibutuhkan variabel tambahan, tentu waktu komputasinya akan lebih lama. Karena itu butuh cara lain untuk menyelesaikannya.

Deskripsi dari Algoritma Euclidean ini adalah sebagai berikut:

Misalkan terdapat dua buah bilangan yaitu dan n, maka GCD/FPB dari kedua bilangan tersebut dapat dihitung dengan langkah berikut:

  1. Bagi bilangan dengan dan anggap adalah sisa bagi dari kedua bilangan tersebut. Nilai dari akan memenuhi 0 <= rn.
  2. Jika nilai = 0, maka algoritma selesai. adalah solusinya. Tapi jika ternyata tidak, maka:
  3. Set nilai menjadi n, dan nilai n menjadi r, kemudian kembali ke langkah 1.

Misalkan, gcd adalah nama fungsi untuk menemukan GCD/FPB dari m dan n, berikut adalah contoh penggunaannya untuk kasus sebelumnya.

m = 24, n = 30
gcd(m, n):
24 / 30 = 0, r = 24
r tidak sama dengan 0, maka

m = n, n = r -> m = 30, n = 24
gcd(m, n):
30 / 24 = 1, r = 6
r tidak sama dengan 0, maka

m = n, n = r -> m = 24, n = 6
gcd(m, n):
24 / 6 = 0, r = 0
karena r = 0, maka hasilnya adalah n.

Jadi gcd(24, 30) = gcd(30, 24) = gcd(24, 6) = 6

Mari mulai coding!🙂

Algoritma tersebut, jika ditulis dalam Bahasa Pascal akan menjadi seperti berikut:

function gcd(m, n : integer) : integer;
var r : integer;
begin
    r := m mod n;

    while (r <> 0) do begin
        m := n;
        n := r;
        r := m mod n;
    end;

    gcd := n;
end;

Sedangkan dalam Bahasa C, berikut penulisannya:

int gcd(int m, int n) {
    int r;

    while((r = m % n) != 0) {
        m = n;
        n = r;
    }

    return n;
}

Algoritma Euclid ini juga bisa ditulis dengan suatu model algoritma rekursif. Hal yang perlu diketahui adalah, pada kasus sebelumnya, jika pada fungsi gcd(m, n) nilai m dimasukkan dengan 0 maka akan secara otomatis nilai akan dikembalikan. Begitu pula sebaliknya, jika pada fungsi gcd(m, n) nilai n dimasukkan dengan 0, maka secara otomatis nilai akan dikembalikan. Dengan kata lain, GCD/FPB dari suatu bilangan dan 0 adalah bilangan itu sendiri.

Berlandaskan pada gagasan tersebut, maka dapat ditarik suatu algoritma rekursif dengan definisi sebagai berikut:

  1. Cek apakah ada di antara m atau n yang sama dengan 0? Jika ada hentikan algoritma dan hasil dari algoritma adalah bilangan yang bukan 0.
  2. Jika baik m dan n tidak ada yang sama dengan 0, maka dengan mengasumsikan bahwa adalah sisa bagi dari bilangan dan n, maka gcd(mn) itu sama dengan gcd(n, r).

Kembali ke coding!🙂

function gcd(m, n : integer) : integer;
begin
    if (m = 0) then
        return n
    else if (n = 0) then
        return m
    else begin
        gcd := gcd(n, m mod n);
    end;
end;

Sedangkan implementasinya dalam bahasa C adalah sebagai berikut:

int gcd(int m, int n) {
    if (m == 0) {
        return n;
    }
    else if (n == 0) {
        return m;
    }
    else {
        return gcd(n, m % n);
    }
}

Untuk menguji bagaimana output-nya, saya menulis program kecil berikut. Silakan dianalisis, dan selamat ber-coding ria.😛

#include <stdio.h>

int gcd(int m, int n) {
    int r;

    while ((r = m % n) != 0) {
        m = n;
        n = r;
     }

     return n;
}

int main() {
    int m, n;

    printf("Press Ctrl + C to exit.\n");
    while (1) {
        printf("Write m and n respectively: ");
        scanf("%d %d", &m, &n);
        printf("gcd(%d, %d) = %d\n", m, n, gcd(m, n));
    }
}

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s