My first Magazine pemrograman-kompetitif-dasar | Page 25

2.3 FPB dan KPK
2.3
FPB dan KPK
Ketika masih SD, kita pernah belajar memfaktorkan bilangan dengan pohon faktor. Melalui
faktorisasi prima, kita dapat menyatakan suatu bilangan sebagai hasil perkalian faktor primanya.
Contoh: 7875 = 3 2 × 5 3 × 7.
Faktor Persekutuan Terbesar (FPB) dan Kelipatan Persekutuan Terkecil (KPK) dapat dicari
melalui faktorisasi prima. Untuk setiap bilangan prima, kita menggunakan pangkat terkecil untuk
FPB dan pangkat terbesar untuk KPK.
Sebagai contoh, diketahui:
• 4725 = 3 3 × 5 2 × 7
• 7875 = 3 2 × 5 3 × 7
Maka:
• FPB(4725, 7875) = 3 2 × 5 2 × 7 = 1525
• KPK(4725, 7875) = 3 3 × 5 3 × 7 = 23625
Sebagai catatan, terdapat pula sifat:
KPK(a, b) =
a × b
FPB(a, b)
Pencarian FPB suatu bilangan menggunakan pohon faktor cukup merepotkan. Kita perlu
mencari faktor prima bilangan tersebut, dan jika faktor primanya besar, tentu akan menghabiskan
banyak waktu. Terdapat algoritma yang dapat mencari FPB(a, b) dalam O(log (min (a, b))), yaitu
Algoritma Euclid. 8
Algoritma ini sangat pendek, dan dapat diimplementasikan dengan mudah seperti pada
Algoritma 7.
Algoritma 7 Algoritma Euclid untuk mencari FPB secara rekursif.
1:
2:
3:
4:
5:
6:
7:
function EUCLID (a, b)
if b = 0 then
return a
else
return EUCLID (b, a mod b)
end if
end function
2.4
Pigeonhole Principle (PHP)
Konsep PHP berbunyi:
Jika ada N ekor burung dan M sangkar, yang memenuhi N > M, maka pasti ada sangkar
yang berisi setidaknya 2 ekor burung.
15