Najib Nasich Blog

Coretan ini adalah coretan lama saya, saya buat ketika duduk di semester 5, mengenai algoritma sederhana untuk mencari FPB. Berikut isi coretannya.

Ada beberapa algoritma untuk menemukan FPB dari dua bilangan, salah satunya adalah dengan Algoritma Euclid. Algoritma ini diciptakan oleh seorang matematikawan Yunani bernama Euclid. Bagaimanakah caranya? Mari kita bahas secara lebih mendalam tentang FPB dan Euclid.

Pengertian
Istilah FPB merupakan istilah Matematika yang merupakan singkatan dari Faktor Persekutuan Terbesar, atau dalam Bahasa Inggris disebut GCD (Greatest Conmmon Divisor)
FPB dari dua bilangan adalah sebuah bilangan bulat positif terbesar yang dapat membagi kedua bilangan tersebut.
Misalkan terdapat 2 bilangan, 24 dan 32.
Bilangan yang dapat membagi 24 adalah : 1, 2, 3, 4, 6, 8, 12, 24
Bilangan yang dapat membagi 32 adalah : 1, 2, 4, 8, 16, 32
1, 2, dan 4, ketiga bilangan ini dapat membagi 24 maupun 32, dan yang dimaksud dengan FPB dari 24 dan 32 adalah 4, karena merupakan bilangan terbesar dari bilangan-bilangan yang dapat membagi kedua bilangan itu.

Algoritma Euclid untuk mencari FPB
Algoritma Euclid merupakan cara yang sangat tepat (menurut saya) untuk mendapatkan nilai FPB dari dua bilangan. Algoritma ini memanfaatkan sifat-sifat dari sisa pembagian atau modulu. Langkah-langkah algoritma Euclid adalah sebagai berikut:

1. A dan B merupakan dua bilangan yang dicari FPB nya.
2. Cari nilai sisa pembagian A terhadap B (A mod B)
3. Jika nilai modulu yang dicari = 0, maka lanjutkan ke langkah 6. Jika tidak 0, maka lanjutkan langkah 4.
4. ubah nilai A menjadi nilai B, dan nilai B menjadi nilai modulu yang dicari sebelumnya.
5. Ulangi langkah 2
6. Nilai FPB yang dicari adalah B.

Perhatikan contoh berikut untuk mengetahui implementasi pencarian FPB menggunakan Euclid.
Pencarian FPB dari 32 dan 12, langkah-langkahnya :

 Dari ilustrasi di atas, maka dengan algoritma Euclid akan didapatkan FPB dari 32 dan 12 adalah 4.
Source Code
Berikut ini adalah source code program yang dapat digunakan untuk mencari FPB dari dua bilangan berdasarkan algoritma yang telah dijelaskan sebelumnya.