[Algorithm] GCD - LCM / FPB - KPK
Categories: Algoritma, Programming | May 13th, 2008 | by Felix J | 10 CommentsGCD - LCM / FPB - KPK… Greatest Common Divisors - Lowest Common Multiples ato Faktor Persekutuan Terbesar - Kelipatan Persekutuan Terkecil adalah salah satu pelajaran matematika yang pernah kita dapatkan sewaktu SD… Masih ingatkah anda? Coba buka-buka lagi dhe buku pas SD dlu 
:P hehehehe… kalo gk ada, yah dengan post ini, saya coba bantu ingatkan anda dengan contoh yang simpel…
Contohnya adalah, “Carilah FPB (GCD) dan KPK (LCM) dari angka 147, 189, dan 231 !”.
Maka langkah awalnya kita adalah buat dluw faktor faktor prima dari angka di atas
147 = 3 x 7²
189 = 3³ x 7
231 = 3 x 7 x 11
Maka Penyelesaiannya,
FPB : 3 x 7 = 21
KPK : 3³ x 7² x 11 = 14553
Jadi, untuk mendapatkan FPB adalah ambil faktor prima dengan pangkat terkecil pada masing2 bilangan yang muncul di smua bilangan yang akan dicari FPBnya, dalam hal ini, 3 dan 7 muncul di kesemua bilangan, sedangkan 11 hanya muncul di bilangan 231. Sehingga 11 tidak diikutsertakan dalam perhitungan FPB. Kemudian, angka 3 yang sebenarnya ada 2 varian, yaitu dengan pangkat 3 dan pangkat 1, diambil hanya yang pangkat 1. Angka 7 yang muncul dengan 2 varian juga, angka 7 dengan pangkat 2 dan angka 7 dengan pangkat 1, diambil hanya pangkat yang terkecil yaitu 1 
Berbeda dengan FPB, KPK mengikutkan semua bilangan yang terlist dan angka yang memiliki pangkat tertinggi, sehingga yang diambil adalah 3 dengan pangkat 3, 7 dengan pangkat 2, dan angka 11
wow… GCD nya simple banget… pernah coba bikin sih tp lbh panjang dari itu kyknya… LCM juga pernah bkn tp ga pake GCD nya sama sekali..
@ Hendri
^o^
ohh.. hehehe… iya, ini namanya Euclidean GCD
sebenarnya bs dibuat lebih singkat lg ^o^
int GCD(int a,int b) {
return (b==0) ? a : GCD(b,a%b);
}
^o^
wew..ada pak felix ni ye….
mo tanya dung tpi….klo a<b apa gak crash ya prognya?thx b4…
@vedro,
Gk dunk, dengan jelas kita tahu bahwa jika a<b maka tentu aja di step rekursi selanjutnya akan dirubah a itu menjadi b, dan b menjadi a… liat contoh ini :
sebut saja jika kita memanggil, GCD(7,13), maka Karena B adalah 13, GCD(7,13) akan return GCD(13,7%13).
Kita tahu bahwa jika a < b, maka a%b = a. maka dari itu, GCD(13,7%13), ekuivalen dengan GCD(13,7) ( See? A > B sekarang
).
Proses berlanjut sampe b == 0, Gitu aja
interesting post, will come back here, bookmarked your site
ternyata GCD pake rekursi simple..
@boen,
yup… GCD bisa dicari dengan cara diatas
You write awsome article, bookmarked
Bung Felix, nyari GCD pake algoritma tadi ada kelemahannya g?
mhon dijawab butuh buat tugas nih
@adi belajar TI,
sayangnya… Tak ada