Program Pascal FPB dengan Algoritma Euclid

Ada algoritma untuk menemukan FPB dari dua bilangan, salah satunya adalah dengan Algoritma Euclid. Algoritma ini diciptakan oleh seorang matematikawan Yunani bernama Euclid.

Deskripsi dari Algoritma Euclid ini adalah sebagai berikut:
Misalkan terdapat dua buah bilangan yaitu a dan b, maka FPB/GCD(Greatest Conmmon Divisor) dari kedua bilangan tersebut dapat dihitung dengan langkah berikut:

1. Bagi bilangan a dengan b, dan anggap r adalah sisa bagi dari kedua bilangan tersebut. Nilai dari r akan memenuhi 0 <=r < n.
2. Jika nilai r = 0, maka algoritma selesai. b adalah hasilnya. Tapi jika ternyata tidak, maka:
3. Set nilai a menjadi b, dan nilai b menjadi r, kemudian mengulangi ke langkah 1. Begitu seterusnya sampai nilai r = 0.

Berikut adalah contoh penggunaan Algoritma Euclid :

a = bilangan 1
b = bilangan 2
r = sisa bagi bilangan 1 dan 2

a = 40
b = 12
40 mod 12 = 3, r = 4
r tidak sama dengan 0, maka
a = b
b = r
r = a mod b

a = 12
b = 4
12 mod 4 = 3, r = 0
r sama dengan 0, maka 
Hasil FPB nya adalah 4

Berikut adalah contoh penggunaan dalam Pascal:

program fpb;
uses wincrt;
var a,b,r:integer;

begin
write('masukkan angka 1: '); readln(a);
write('masukkan angka 2: '); readln(b);

r := m mod n;

while (r <> 0) do begin
a := b;
b := r;
r := a mod b;
end;
    writeln('FPB nya adalah ',b);
end.

Secreenshot hasil: