apa itu GCD????

Apa itu GCD??

GCD itu singkatan dari greatest common divisor.. Artinya bilangan terbesar yang dapat membagi dua bilangan atau beberapa bilangan. Istilah Indonesia yang lebih umum di telinga kita adalah FPB (Faktor Persekutuan Terbesar).. Di sini, sebaiknya kita terbiasa menggunakan istilah GCD, karena lebih internasional.

Contoh:
GCD (24,12)=12 (Artinya 12 merupakan bilangan terbesar yang membagi 24 dan 12)
GCD (24,9)= 3 (Artinya 3 merupakan bilangan terbesar yang membagi 24 dan 9)

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
Cara menentukan GCD:
Banyak Cara yang bisa dilakukan untuk menentukan GCD:

1. Ubah ke bentuk perkalian bilangan prima berpangkat. Lalu pilih pangkat terendah.

Contoh soal 1: Tentukan GCD (2520,2646)!
Jawab: 2520 = 23 x 32 x 5 x 7
           2646 = 2 x 33 x 72
Jadi, GCD (2520,2646) = 2 x 32 x7 = 126

2. Mirip cara pertama, tapi gunakan tangga bersusun.. Bagi bilangan-bilangan dengan bilangan x (biasanya mulai dari prima terkecil hingga terbesar).. Tandai bilangan x jika x bisa membagi semua bilangan (misalnya dengan bintang). Ulangi pembagian hingga bilangan-bilangan yang dibagi sudah mencapai angka 1. Lalu, kalikan semua bilangan yang sudah ditandai. Hasil kalinya itulah GCD-nya..
Contoh soal 2: Tentukan GCD (9240,7150)!
Jawab:
Tanda bintang menunjukkan bahwa kedua bilangan habis dibagi..
Jadi, GCD (9240,7150)=2 x 5 x 11 = 110

kalo soal diatas kan cuma ribuan atau ratusan kan??nahh kalo temen temen dapet yang sampe ratus ribuann??gimana ga bingung n puyeng ngliat bilangannya,,
untuk mempermudahprogram dibawah bisa digunakan..


3. Gunakan Algoritma Euclidean

4. Gunakan Algoritma Stein (Binary GCD Algorithm)
thanks to :
http://hendrydext.blogspot.com/2008/09/gcd-euclid-dan-binary.html