Euklido algoritmas

Straipsnis iš Vikipedijos, laisvosios enciklopedijos.

Euklido algoritmas - algoritmas, kurio autorystė prisikiriama Euklidui, skirtas surasti dviejų skaičių didžiausią bendrą daliklį.

Algoritmas dviejų skaičių A ir B DBD rasti užrašomas taip:

  • Jeigu B yra nulis, tuomet DBD yra A
  • Kitaip,
  • AB
  • BA dalybos iš B liekana
  • Kartojame nuo pirmo žingsnio