Deo zbornika Učimo algoritme

Euklidov algoritam

Email Twitter LinkedIn Facebook Google

Euklidov algoritam je efikasan način za određivanje najvećeg zajedničkog delioca (NZD) dva broja. Nazvan je po starogrčkom matematičaru Euklidu, koji ga je naveo u VII i X knjizi svojih Elemenata (oko 300. p.n.e.).

Prema rečima Donalda Knuta, „Euklidov algoritam je deda svih algoritama, pošto je najstariji netrivijalni algoritam koji je preživeo do danas.

Sled koraka

Euklidov algoritam otkriva najveći zajednički delilac dva broja tako što od većeg neprestano oduzmimamo manji.

Na primer, imamo brojeve 48 i 18. Ukoliko od 48 oduzmemo 18 dobićemo 30, dakle, ostaju nam 30 i 18. Zatim od 30 oduzimamo 18, pa imamo 12 i 18. Ponavljamo ovaj postupak dok jedan od brojeva ne postane nula. Na kraju, jedini preostali broj (6) je najveći zajednički delilac.

Iterativna implementacija

function nzd(a, b) {
  while (b != 0)
    [a, b] = [b, a % b]
  return a
}

console.log(nzd(48, 18))

Rekurzivna implementacija

Najveći zajednički delilac se, pomoću Euklidovog algoritma, može izračunati narednom rekurzivnom funkcijom:

function nzd(a, b) {
  if (b == 0) return a
  return nzd(b, a % b)
}

console.log(nzd(48, 18))