Dalam dunia matematika dan pemrograman, mencari Faktor Persekutuan Terbesar (FPB) dan Kelipatan Persekutuan Terkecil (KPK) dari dua bilangan atau lebih adalah operasi fundamental yang sering ditemui. Memahami algoritma yang efisien untuk menghitung keduanya sangat penting, terutama ketika berhadapan dengan data yang besar atau dalam aplikasi yang membutuhkan performa tinggi. Artikel ini akan mengupas tuntas algoritma-algoritma tersebut, mulai dari konsep dasar hingga implementasinya.
FPB dari dua bilangan bulat non-nol, katakanlah a dan b, adalah bilangan bulat positif terbesar yang dapat membagi habis kedua bilangan tersebut tanpa sisa. Misalnya, FPB dari 12 dan 18 adalah 6, karena 6 adalah bilangan terbesar yang bisa membagi 12 (12 / 6 = 2) dan 18 (18 / 6 = 3).
Algoritma Euclid adalah metode paling klasik dan efisien untuk menemukan FPB. Prinsipnya didasarkan pada fakta bahwa FPB dari dua bilangan tidak berubah jika bilangan yang lebih besar diganti dengan selisihnya dari bilangan yang lebih kecil. Proses ini diulang sampai salah satu bilangan menjadi nol, dan bilangan yang bukan nol adalah FPB-nya.
Versi yang lebih umum dan efisien dari Algoritma Euclid menggunakan operasi modulo (sisa pembagian). Algoritma ini menyatakan bahwa FPB(a, b) sama dengan FPB(b, a mod b), dengan asumsi a lebih besar dari b. Proses ini dilanjutkan hingga b menjadi 0, maka FPB-nya adalah a.
Contoh pencarian FPB(48, 18):
Implementasi sederhana dalam pseudocode:
fungsi FPB_Euclid(a, b):
while b != 0:
sisa = a mod b
a = b
b = sisa
return a
KPK dari dua bilangan bulat positif, katakanlah a dan b, adalah bilangan bulat positif terkecil yang merupakan kelipatan dari kedua bilangan tersebut. Misalnya, KPK dari 4 dan 6 adalah 12, karena 12 adalah bilangan positif terkecil yang habis dibagi 4 (12 / 4 = 3) dan habis dibagi 6 (12 / 6 = 2).
Ada hubungan matematis yang sangat berguna antara FPB dan KPK dari dua bilangan. Untuk dua bilangan bulat positif a dan b, berlaku rumus:
a * b = FPB(a, b) * KPK(a, b)
Dari rumus ini, kita dapat dengan mudah menurunkan rumus untuk mencari KPK jika FPB sudah diketahui:
KPK(a, b) = (a * b) / FPB(a, b)
Keuntungan menggunakan rumus ini adalah kita hanya perlu menghitung FPB menggunakan Algoritma Euclid yang efisien, kemudian menghitung KPK dengan satu operasi perkalian dan satu operasi pembagian. Ini jauh lebih cepat daripada metode mencari kelipatan satu per satu, terutama untuk bilangan besar.
Contoh pencarian KPK(48, 18):
Kita sudah tahu dari contoh sebelumnya bahwa FPB(48, 18) = 6.
Maka, KPK(48, 18) = (48 * 18) / FPB(48, 18) = 864 / 6 = 144.
Implementasi sederhana dalam pseudocode untuk KPK menggunakan FPB:
fungsi KPK(a, b):
if a == 0 or b == 0:
return 0 // KPK dengan nol adalah nol
fpb_nilai = FPB_Euclid(a, b)
return (a * b) / fpb_nilai
Meskipun Algoritma Euclid dan rumus yang terkait adalah yang paling efisien, perlu diketahui bahwa ada metode lain:
Metode-metode ini lebih mudah dipahami secara konseptual tetapi kurang praktis untuk penggunaan dalam skala besar.
Memahami dan menerapkan Algoritma Euclid untuk mencari FPB, serta memanfaatkan hubungannya dengan KPK melalui rumus KPK(a, b) = (a * b) / FPB(a, b), adalah kunci untuk menghitung kedua nilai ini secara efisien. Pendekatan ini tidak hanya meminimalkan jumlah operasi komputasi tetapi juga memberikan solusi yang handal untuk berbagai masalah matematika dan pemrograman. Dengan implementasi yang tepat, Anda dapat memastikan kinerja optimal dalam aplikasi Anda.