Mencari FPB dan KPK Tercepat

EUCLID ALGORITHM

Pengertian :

FPB = Faktor Persekutuan Terkecil. Antara dua bilangan, FPB dari kedua bilangan adalah bilangan bulat positif terbesar yang membagi habis kedua bilangan tersebut.

KPK = Kelipatan Persekutan Terkecil. Antara dua bilangan, KPK dari kedua bilangan adalah bilangan bulat positif terkecil yang merupakan kelipatan dari kedua bilangan tersebut.

Secara singkat, untuk bilangan bulat positif A, dan B, berlaku :

A*B = FPB(A,B) * KPK(A,B)

Sehingga, untuk mencari KPK kita cukup mencari FPB saja, dan nilai KPK adalah:

KPK(A,B) = A*B / FPB(A,B)

Untuk mencari FPB, kita akan menggunakan Algoritma Euclid, yang dikenal efektif dan cepat.

Contoh Penggunaan Algoritma Euclid : 

1. Misal ada dua bilangan, A = 14, dan B = 21. Kita akan menghitung FPB nya.

    Formula = B = A*K + S  //Keterangan : K adalah Hasil Pembagian  dan S adalah Sisa Pembagian

    Step 1 :

    21 = 14*1 + 7 //Disini K=1, dan S = 7

    A nilainya kita update jadi B

    B nilainya kita update jadi S

    

    Step 2 :

    Ulangi Step 1 sampai S bernilai 0

    14 = 7*2 + 0 //Disini kebetulan nilai S = 0, jadi kita stop dan FPB nya adalah nilai B yaitu 7

    Jika ternyata S belum 0, maka ulangi step 1.

    Jawab : 7

2. Hitung FPB dari 12827 dan 7493.

    Step 1:

    12827 = 7493*1 + 5334

    Step 2:

    7493 = 5334*1 + 2159

    Step 3:

    5334 = 2159*2 + 1016

    Step 4:

    2159 = 1016*2 + 127

    Step 5:

    1016 = 127*8 + 0

    Maka FPB dari 12827 dan 7493 adalah 127

Berikut Code nya dalam Python dan C++

1. Python

2. C++

//Catatan : untuk bilangan yang besar (lebih dari batas integer yaitu 2.147.483.647, kita bisa gunakan tipe data "long long"

Lalu gimana caranya menghitung KPK ?

untuk menghitung KPK kita tetap menyertakan fungsi euclid untuk menemukan FPB nya, lalu tinggal gunakan rumus ini :

KPK(A,B) = A*B / FPB(A,B)