Mencari Faktor Persekutuan Terbesar

Soal :
Tulislah program untuk menghitung FPB dari dua bilangan bulat.
Masukkan dari program ini adalah dua bilangan bulat bertipe integer.
keluaran dari program ini FPB dari dua bilangan diatas.

pembahasan :

algoritma yang digunakan untuk mencari FPB dari dua bilangan bulat adalah algoritma Euclid. untuk menjelaskan algoritma ini akan mulai dengan contoh sederhana. misalkan ingin mencari FPB dari 228 dan 90. langkah-langkah pencarian FPB dapat dituliskan sebagai berikut :
228 / 90 = 2 sisa 48
90 / 48 = 1 sisa 42
48 / 42 = 1 sisa 6
42 / 6 = 7 sisa 0

karena sisa pembagian yang terakhir sebelum 0 adalah 6, maka FPB dari 228 dan 90 adalah 6
Algoritma Pencarian FPB dari dua bilangan m dan n adalah sebagai berikut :

1. Masukkan m,n.
   
2. Kerjakan baris 3 dan 4 sampai (r = 0).
   
3. r = m mod n
   
4. Jika (r <> 0) maka n → m; r → n.
5. Tulis n

program adalah sebagai berikut :

uses
wincrt;

var m,n,r : integer;

begin
write('Masukkan bilangan pertama :'); readln(m);
write('Masukkan bilangan Kedua :');readln(n);

repeat
r := m mod n;
if( r <> 0) then
begin
m := n;
n := r;
end;

until ( r = 0);
writeln('FPB:',n);
end.

Bookmark this post: