Algoritma Euclidean (Euclidean Algorithm)

 Algoritma ini merupakan algoritma tertua sepanjang sejarah. Algoritma ini disebarkan sejak 300 BC oleh Euclid dalam tulisannya berjudul Euclid's Element. 

Algoritma ini khususnya berlaku untuk mencari GCD dari 2 bilangan, dan sangat cocok diterapkan dalam pemrograman komputer karena sifatnya yang dinamis (tidak perlu mencari bilangan prima lagi). Konsep algoritma ini: bilangan yang lebih besar (p) dibagi dengan bilangan yang lebih kecil (q). Jika tak bersisa, GCD-nya adalah q. Jika bersisa, lakukan perulangan lagi. Kali ini, q dibagi dengan r(sisa).. Lalu, lakukan terus perulangan pembagian hingga didapat sisanya 0. Maka, GCD-nya adalah bilangan terakhir yang menjadi remainder (sisa).

Contoh soal 3: Tentukan GCD (16524, 73756)!
Jawab:
73756 = 4 x 16524 + 7660
16524 = 2 x 7660 + 1204
7660 = 6 x 1204 + 436
1204 = 2 x 436 + 332
436 = 1 x 332 +104
332 = 3 x 104 + 20
104 = 5 x 20 + 4
20 = 5 x 4 + 0

Karena remainder terakhir adalah 0, maka GCD dari 16524 dan 73756 adalah remainder/sisa sebelumnya, yaitu 4.
GCD (16524, 73756) = 4.

Contoh soal 4: Tentukan GCD(1353,1716)!
Jawab:
1716 = 1 x 1353 + 363
1353 = 3 x 363 + 264
363 = 1 x 264 + 99
264 = 2 x 99 + 66
99 = 1 x 66+ 33
66 = 2 x 33 +0

Jadi, GCD (1353,1716) = 33.