Öklid algoritması: en büyük ortak bölen

Kısaca: İki sayının en büyük ortak bölenini (ebob) tekrarlanan kalanlı bölmeyle hesaplayan, çok eski ve hızlı bir yöntem.

Biraz daha ayrıntılı: 48 ile 18’in ebob’u 6’dır, ikisini de bölen en büyük sayı. Tüm bölenleri sıralamak yerine Öklid (MÖ 300 dolayı) şu gözleme dayanır: ebob(a, b) = ebob(b, a mod b). Çifti (b, kalan) ile değiştirir ve kalan 0 olana kadar yinelersiniz. Sıfırdan farklı son sayı ebob’dur.

Ayrıntılı

Örnek

ebob(48, 18):

48 mod 18 = 12

Ayrıca bak: Özyineleme, Büyük O gösterimi, Algoritmalar