Visualisasi sederhana Algoritma Euclid
Dalam dunia matematika dan ilmu komputer, menemukan Faktor Persekutuan Terbesar (FPB) dari dua bilangan adalah tugas yang sering muncul. FPB adalah bilangan bulat positif terbesar yang dapat membagi habis kedua bilangan tersebut tanpa sisa. Metode tradisional untuk menemukan FPB mungkin melibatkan pencarian semua faktor dari masing-masing bilangan, kemudian membandingkannya. Namun, pendekatan ini bisa menjadi sangat lambat, terutama untuk bilangan yang besar. Di sinilah Algoritma Euclid hadir sebagai solusi yang elegan dan sangat efisien.
Algoritma ini dinamai sesuai dengan nama seorang matematikawan Yunani kuno, Euclid, yang menyebutkannya dalam karyanya "Elements" sekitar 300 SM. Meskipun ia tidak mengklaim sebagai penemunya, Euclid adalah orang pertama yang mendokumentasikannya secara sistematis. Algoritma ini telah digunakan selama ribuan tahun dan tetap menjadi salah satu algoritma paling dasar dan penting dalam teori bilangan.
Inti dari Algoritma Euclid terletak pada prinsip sederhana: FPB dari dua bilangan tidak berubah jika bilangan yang lebih besar diganti dengan selisih antara kedua bilangan tersebut. Namun, versi yang lebih umum dan lebih efisien menggunakan operasi modulo (sisa pembagian). Prinsipnya adalah sebagai berikut:
Misalkan kita memiliki dua bilangan bulat non-negatif a dan b, dengan a > b. Jika b = 0, maka FPB(a, b) adalah a. Jika b > 0, maka FPB(a, b) sama dengan FPB(b, a mod b), di mana a mod b adalah sisa dari pembagian a oleh b.
Proses ini diulang terus menerus, dengan mengganti pasangan bilangan menjadi bilangan yang lebih kecil pada setiap langkah. Ketika sisa pembagian menjadi nol, maka pembagi pada langkah sebelumnya adalah FPB dari kedua bilangan awal.
Mari kita cari FPB dari 48 dan 18 menggunakan Algoritma Euclid:
a = 48, b = 18.a oleh b: 48 mod 18 = 12.b = 18 dan sisanya 12. Jadi, a = 18, b = 12.18 mod 12 = 6.a = 12, b = 6.12 mod 6 = 0.Karena sisanya adalah 0, maka FPB dari 48 dan 18 adalah pembagi pada langkah terakhir sebelum sisa menjadi nol, yaitu 6.
Algoritma ini dapat dengan mudah diimplementasikan dalam berbagai bahasa pemrograman, baik secara iteratif maupun rekursif.
Versi iteratif menggunakan loop untuk terus mengulang proses sampai sisa pembagian menjadi nol.
function gcdIteratif(a, b) {
while (b !== 0) {
let temp = b;
b = a % b;
a = temp;
}
return a;
}
Versi rekursif memanggil dirinya sendiri dengan argumen yang diperbarui.
function gcdRekursif(a, b) {
if (b === 0) {
return a;
} else {
return gcdRekursif(b, a % b);
}
}
Ada beberapa alasan mengapa Algoritma Euclid sangat dihargai:
Algoritma Euclid adalah bukti nyata bahwa solusi yang kompleks dapat berasal dari prinsip-prinsip yang sederhana. Dengan memanfaatkan operasi modulo secara berulang, algoritma ini menawarkan cara yang sangat efisien dan andal untuk menghitung Faktor Persekutuan Terbesar dari dua bilangan. Keandalannya telah memastikan tempatnya sebagai salah satu pilar penting dalam matematika dan ilmu komputer.