Chase The Limit

[Algorithm] GCD - LCM / FPB - KPK

Categories: Algoritma, Programming | May 13th, 2008 | by Felix J | 10 Comments

LCM membutuhkan algoritma GCD diatas.. Ternyata setelah diteliti, LCM pun memiliki algoritma yang lebih cepat yaitu,
LCM(a, b) = (a*b) / GCD(a, b)

Mari kita buktikan… Kita tetap memakai 2 bilangan diatas, yaitu 24 dan 20… Menurut rumus LCM tersebut maka
LCM(24, 20) = (24 * 20) / GCD(24, 20)

Seperti kita ketahui, GCD(24, 20) adalah 4 maka kita sederhanakan saja persamaan diatas menjadi
LCM (24, 20) = (24 * 20) / 4

Dengan sifat pembagian, maka kita coba sederhanakan lagi menjadi
LCM(24, 20) = ((24 / 2) * (20 / 2))
LCM(24, 20) = (12 * 10)
LCM(24, 20) = 120

Apakah benar? Mari kita coba lagi dengan matematik ‘Anak SD’ lagi untuk membuktikannya… Mari Kita lihat lagi Faktor Prima kedua angka tersebut yang sudah tertulis diatas… maka LCM dari ke-2 bilangan ini dapat disusun menjadi

LCM(24, 20) = 2³ x 3 x 5 = 8 x 3 x 5 = 40 x 3 = 120

Terbukti kan? oleh karena itu, maka kita dapat membuat Kode LCM dari kode persamaan diatas

int LCM(int a, int b)
{
	return ((a*b) / GCD(a,b));
}

Maka dengan ini, selesailah sudah pelajaran untuk hari ini hehehe…

Akhir kata, Semoga artikel ini bermanfaat bagi anda sekalian

- Felix J

Pages: 1 2 3 4

10 Responses to “[Algorithm] GCD - LCM / FPB - KPK”

Posted @ 07 Oct 2008 at 3:23 pm1. Hendri

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..
Posted @ 07 Oct 2008 at 10:59 pm2. Felix J

@ Hendri
ohh.. hehehe… iya, ini namanya Euclidean GCD ^o^
sebenarnya bs dibuat lebih singkat lg ^o^

int GCD(int a,int b) {
return (b==0) ? a : GCD(b,a%b);
}

^o^
Posted @ 12 Apr 2009 at 6:54 pm3. Vedro E.C

wew..ada pak felix ni ye….
mo tanya dung tpi….klo a<b apa gak crash ya prognya?thx b4…
Posted @ 12 Apr 2009 at 9:50 pm4. Felix J

@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
Posted @ 01 Jul 2009 at 4:26 am5. ekspekt

interesting post, will come back here, bookmarked your site
Posted @ 07 Oct 2009 at 10:36 am6. boen

ternyata GCD pake rekursi simple..
Posted @ 04 Nov 2009 at 9:12 pm7. Felix J

@boen,
yup… GCD bisa dicari dengan cara diatas
Posted @ 24 Dec 2009 at 10:57 pm8. luki sportowe

You write awsome article, bookmarked
Posted @ 25 Feb 2010 at 2:51 pm9. adi belajar TI

Bung Felix, nyari GCD pake algoritma tadi ada kelemahannya g?
mhon dijawab butuh buat tugas nih
Posted @ 28 Feb 2010 at 11:20 am10. Felix J

@adi belajar TI,
sayangnya… Tak ada