Algorytm Euklidesa – algorytm znajdowania największego wspólnego dzielnika (NWD) dwóch liczb naturalnych, nie wymagający rozkładania ich na czynniki pierwsze. Jego autorem jest Eudoksos z Knidos (IV wiek p.n.e.), Euklides zawarł go jedynie w swoim dziele Elementy.

Podstawą algorytmu Euklidesa jest zależność:

Algorytm

Istnieją dwie równoważne implementacje algorytmu Euklidesa. Poniżej przedstawiono wersję obliczania NWD liczb a i b wykorzystującą operację reszty z dzielenia (modulo):

1. oblicz c jako resztę z dzielenia a przez b
2. zastąp pozycję a liczbą b, a pozycję b liczbą c
3. jeżeli pozycja b = 0, to szukane NWD = a, w przeciwnym wypadku przejdź do 1

Implementacja

Pseudokod

  NWD(liczba całkowita a, liczba całkowita b)
       dopóki b != 0
           c := reszta z dzielenia a przez b        
           a := b
           b := c
       zwróć a

C++

int NWD (int a, int b)
{
    int c;
    while (b != 0)
    {
          c = a % b;
          a = b;
          b = c;
 
    }
    return a;
}

Wersja rekurencyjna:

int NWD (int a, int b)
{
    a=a%b;
    if(a!=0)
       return NWD(b,a);
    else
       return b;
}

C#

static int NWD(int a, int b)
{
    int c;
    while (b != 0)
    {
          c = a % b;
          a = b;
          b = c;
 
    }
    return a;
}

JavaScript

function NWD(a, b) {
   while (b != 0) {
      var c = a % b;
      a = b;
      b = c;
   }
   return a;
}

PHP

function NWD ($a,$b)
{
    $c=0;
    while ($b != 0)
    {
          $c = $a % $b;
          $a = $b;
          $b = $c;
 
    }
    return $a;
}

Pascal

Wersja algorytmu wykorzystująca operację odejmowania:

function nwd(a,b:integer):integer;
 begin
   while a<>b do
     if a>b then a:=a-b else b:=b-a;
   nwd:=a;
 end;

Prolog

nwd(A,0,A) :- !.
nwd(A,B,C) :- B1 is A mod B, nwd(B,B1,C).

Python

Wersja algorytmu wykorzystująca operację odejmowania:

def nwd(a,b):
    while a != b:
        if a > b:
            a = a - b
        else:
            b = b - a
    return a

Asembler

section .text
global getgcd
getgcd:
  push ebp           
  mov  ebp,esp      
  mov  eax,[ebp+8]  
  mov  ebx,[ebp+12] 
petla:
  cmp  eax,ebx     
  jg   wiekszy    
  jl   mniejszy    
  jmp  koniec     
wiekszy:
  sub  eax,ebx
  jmp  petla
mniejszy:
  sub  ebx,eax
  jmp  petla
koniec:
  mov  esp,ebp     
  pop  ebp         
  ret

Logo

  oto nwd :a :b
     dopóki [nie :b = 0] 
       [przypisz "c reszta :a :b
        przypisz "a :b
        przypisz "b :c]
     wynik :a
  już

Wersja rekurencyjna:

  oto nwd :a :b
     przypisz "a reszta :a :b  
     jeżeli nie :a = 0
        [wynik nwd :b :a]
        [wynik :b]
  już