Euklides pierwotnie sformułował ten problem geometrycznie, jako szukanie wspólnej "miary" dwóch odcinków. Jego algorytm polegał na kolejnym odejmowaniu krótszego odcinka od dłuższego.

Implementacja algorytmu Euklidesa

Asembler ARM loop CMP Ri, Rj ; porównaj i z j, ustawiając flagi warunkowe: ; - "GT" dla (i > j) ; - "LT" dla (i < j) ; - "NE" dla (i != j) SUBGT Ri, Ri, Rj ; jeśli "GT" (większa niż ang. greater than), wykonaj i := i - j; SUBLT Rj, Rj, Ri ; jeśli "LT" (mniejsza niż ang. less than), wykonaj j := j - i; BNE loop ; jeśli "NE" (nie równy ang.not equal), wykonaj skok do etykiety 'loop'

NASM x86 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

ActionScript function nwd(a, b) { while (a != b) { if (a>b) { a -= b; } else { b -= a;

return a; }

C/C++, C#, Java int gcd(int a,int b){ return b?gcd(b,a%b):a; } int nwd(int a, int b) { if (b == 0) return a; return nwd(b, (a % b)); } int nwd(int a, int b){ int tmp; while(b != 0){ tmp = a % b; a = b; b = tmp;

return a; }

albo za pomocą odejmowania:

while (i != j) { if (i > j) i -= j; else j -= i; }

MARIE

Input / AC = wejscie Store X / X = AC Input / AC = wejscie Store Y / Y = AC While, Load X / AC = X Subt Y / AC -= Y Skipcond 400 / If (AC==0) [X!=Y] to pomin nast. rozkaz Jump If / If (X!=Y) skocz do If Jump Return / If (X==Y) to wyjdz z petli If, Skipcond 800 / If (AC>0) [X>Y] to pomin nast. rozkaz Jump Else / If (X<Y) to skocz do Else Load X / AC = X Subt Y / AC -= Y Store X / X = AC Jump While / skocz do While (petla) Else, Load Y / AC = Y Subt X / AC -= X Store Y / Y = AC Jump While / skocz do While (petla) Return, Load X / AC = X Output / daj AC na wyjscie Halt / koniec X, dec 0 Y, dec 0

Pascal

Można to zilustrować następującą implementacją w Pascalu.

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;

albo nieco inaczej:

function nwd(a, b: Integer): Integer; var tmp: Integer; begin repeat tmp := a mod b; a := b; b := tmp; until b = 0; nwd := a; end;

Perl

sub nwd { my ($a,$b)=@_; # drugi argument nie powinien być większy od pierwszego ($b,$a)=($a,$b) if $b>$a; return $a if $b==0; nwd($b,$a%$b);

PHP

function NWD($a, $b) { while ($b) { $tmp = $a%$b; $a = $b; $b = $tmp;

return $a; }

Javascript

function nwd(a, b) { var r; while (b) { r = a % b; a = b; b = r;

return a; }

Prolog nwd(X,0,X). nwd(X,Y,Wynik):- not(Y==0), X1 is X mod Y, nwd(Y,X1,Wynik1), Wynik is Wynik1.

Python

def nwd(a, b): while b: a, b = b, a%b return a

Wersja uproszczona.

def nwd(a, b): while b: c = b b = a%b a = c return a

Wersja z odejmowaniem "odcinków" w Pythonie.

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

Ruby

def bgcd(a,b) g=1 while(a&1==0 && b&1==0) g>=1 b>>=1 end while b!=0 if a&1 == 0 a>>=1 elsif b&1 == 0 b>>=1 else if (a>b) a-=b a>>=1 else b-=a b>>=1 end end end return g*a end

def nwd(a,b) if a > b then a -= b else b -= a end while a != b; return a end dla wielu liczb gdzie arr - tablica liczb def nwd(arr) a = arr.pop arr.each do |b| if a > b then a -= b else b -= a end while a != b; end return a end Funkcja biblioteki standardowej: a.gcd b

Scheme

Definicja funkcji wynika bezpośrednio ze wzoru rekurencyjnego:

(define (nwd a b) (if (= b 0) a (nwd b (modulo a b))))

(define (mod a b) (if( 0 select @tmp = @a%@b, @a = @b, @b = @tmp return @a end

Dla większej ilości liczb

PHP function gcdp($a, $b) { // funkcja pomocnicza if ($b == 0) { return $a; } else { return gcdp($b, $a % $b);

function gcd($list) { // główna funkcja sort($list); $g = $list; for ($i = 0; $i < count($list)-1; $i++) { $g = gcdp($g, $list[$i]);

return $g; }

Rozszerzony algorytm Euklidesa

SQL

create function nwd(@a int, @b int) returns @m table(p int, q int) /* Funkcja zwraca rozwiązanie równania: a*p + b*q = NWD(a,b) */ as begin declare @r int, @q int, @x int, @x1 int, @x2 int, @y int, @y1 int, @y2 int

select @q = @a/@b, @r = @a - @q*@b, @x2 = 1, @x1 = 0, @x = 1, @y2 = 0, @y1 = 1, @y = 1 - @q

while @r <> 0 select @a = @b, @b = @r, @x = @x2 - @q*@x1, @x2 = @x1, @x1 = @x, @y = @y2 - @q*@y1, @y2 = @y1, @y1 = @y, @q = @a/@b, @r = @a - @q*@b

insert into @m select @x, @y

return end

C++

#include #include

int main (){ int a,b;

//Pobranie danych std::cout > a; std::cout > b; if ( (a < 0) || (b < 0) ){ std::cout << "Wartosci a i b powinny byc wieksze od zera\n"; exit (1);

//zachowanie pierwotnych wartosci int a0 = a, b0 = b;

//Zapewnia spelnienie niezmiennika p*a0 + q*b0 = a oraz r*a0 + s*b0 = b int p = 1, q = 0, r = 0, s = 1; int c, quot, new_r, new_s;

//algorytm while (b != 0){ c = a % b; quot = lrint (floor (a/b)); a = b; b = c; new_r = p - quot * r; new_s = q - quot * s; p = r; q = s; r = new_r; s = new_s;

std::cout

int v,w;

template struct tripl { // wzorowane na kontenerze pair z biblioteki STL _t1 d; _t2 x; _t3 y; tripl() : d(), x(), y() { }; tripl(const _t1& _a, const _t2& _b, const _t3& _c) : d(_a), x(_b), y(_c) { }; template tripl(const tripl& _t) : d(_t.d), x(_t.x), y(_t.y) { };

template tripl egcd(typ _a, typ _b) { // szablon funkcji obliczającej NWD if(_b==0) return tripl(_a,1,0); tripl tmp; tmp = egcd(_b,_a%_b); return tripl (tmp.d, tmp.y, tmp.x-((int)(_a/_b))*tmp.y); }

int main() { std::cout > v >> w; tripl ret; ret = egcd(v,w); std::cout 0? " + " : " - ") 0? ret.y : -ret.y) << "*" << w << '\n'; return 0; }