fpb gcd dengan cepat

FPB atau faktor persekutuan terbesar dalam bahasa asingnya GCD(Greatest Common Divisor ) adalah bilangan terbesar yang membagi habis 2 atau lebih bilangan..
misalnya saja FPB 10 dan 8 adalah 2 karena 2 bilangan terbesar yang membagi habis 10 dan 8. FPB yang paling kecil adalah 1. karena 1 dapat membagi semua bilangan. yang menghasilkan FPB 1 itu misalnya FPB antara dua bilangan prima..
FPB 13 dan 11 sudah pasti 1..

biasanya dalam sd diperkenalkan adalah dengan cara pohon faktorial.. seperti gambar dibawah ini

             147         189             231
              /\          /\              /\
             3 49        3  63           3  77
               /\           /\              /\
              7  7         3  21            7  11
                              /\
                             3  7

pertama tama membagi bilangan dengan 2 kalo tidak habis dibagi 2 pindah ke 3 dan seterusnya.. kalo habis dibagi lagi dengan bilangan yang sama masih bisa atau enggak.. kalo tidak ganti ke urututan berikutnya... urutannya 2,3,5,7,11,13 mengikuti bilangan prima..  kita lihat angka terbesar yang dimiliki  ketiganya.. kalo diatas adalah 7.. karena 7 adalah angka terbesar yang dimiliki ketiga tiganya.. beda dengan 11 yang dimiliki cuma 231.. dan 3 bukanlah angka yang terbesar karena masih ada 7

namun cara itu cukuplah lama.. ada cara yang paling cepat yaitu dengan menggunakan algoritma eclide..
caranya
1. pilih yang paling kecil antara 2 bilangan.. misal 147 dan 189.. kita pilih 147
2. ambil hasil sisa bagi(modulo) yang terbesar dengan yang terkecil.. 189 mod 147 = 42
3. yang terkecil tadi dibagi hasil sisa bagi.. 147 mod 42 = 7
4. balik ke langkah 2 sampai hasil baginya = 0.. 42/7=0
5. modulo yang membagi itulah hasil FPBnya dalam hal ini 7

contoh lain
- 10 dan 8.. 10%8 = 2 -> 8%2=0 -> FPB=2
- 100 dan 90.. 100%90=10 -> 90%10=0 -> FPB=10

gampang kan..
sumber http://id.wikipedia.org/wiki/Faktor_persekutuan_terbesar