jednake([],[]).
jednake([_|R1],[_|R2]):-jednake(R1,R2).

duzina([],0).
duzina([X|R],D):-duzina(R,D1),D is D1+1.

kraca(L,R,L):-duzina(L,N1),duzina(R,N2),N1<N2,!.
kraca(L,R,R):-duzina(L,N1),duzina(R,N2),N1>N2,!.

manja([],[],[]).
manja([X|R1],[X1|R2],[X|R1]):-jednake([X|R1],[X1|R2]),X<X1.
manja([X|R1],[X1|R2],[X1|R2]):-jednake([X|R1],[X1|R2]),X>X1.
manja([X|R1],[X1|R2],[X|L]):-jednake([X|R1],[X1|R2]),X=:=X1,manja(R1,R2,L),!.
manja(R1,R2,L):-kraca(R1,R2,L).

nzd1(L,L,L,Osn).
nzd1(L,R,D,Osn):-manja(L,R,L),oduzmi(R,L,C,Osn),nzd1(L,C,D,Osn).
nzd1(L,R,D,Osn):-manja(L,R,R),oduzmi(L,R,C,Osn),nzd1(R,C,D,Osn).

produzi(R,N,R):-duzina(R,N).
produzi(R,N,[0|L]):-duzina(R,N1),N1<N,N2 is N-1,produzi(R,N2,L).

oduzmi(L1,L2,Lx,Osn):-duzina(L1,N),produzi(L2,N,R),oduzmi(L1,R,L,P1,Osn),brisi0(L,Lx).
oduzmi([X],[Y],[C],0,Osn):-X>=Y,C is X-Y.
oduzmi([X],[Y],[C],1,Osn):-X<Y,C is Osn+X-Y.
oduzmi([X1|R1],[X2|R2],[C|L],P1,Osn):-oduzmi(R1,R2,L,P,Osn),X1-P>=0,X1-P>=X2,C is X1-P-X2,P1 is 0.
oduzmi([X1|R1],[X2|R2],[C|L],P1,Osn):-oduzmi(R1,R2,L,P,Osn),X1-P<0,C is Osn-P+X1-X2,P1 is 1.
oduzmi([X1|R1],[X2|R2],[C|L],P1,Osn):-oduzmi(R1,R2,L,P,Osn),X1-P>=0,X1-P<X2,C is Osn+X1-P-X2,P1 is 1.


brisi0([],[]).
brisi0([G|L],[G|L]):-G=\=0,!.
brisi0([0|L],K):-brisi0(L,K).

cifra(a,10).
cifra(b,11).
cifra(c,12).
cifra(d,13).
cifra(e,14).
cifra(f,15).

prebaci([],[]).
prebaci([G|L],[G1|L1]):-not(integer(G)),cifra(G,G1),prebaci(L,L1).
prebaci([G|L],[G|L1]):-integer(G),prebaci(L,L1).                      

nzd(Lista1,Lista2,Rez,Osnova):-prebaci(Lista1,ListaX),prebaci(Lista2,ListaY),nzd1(ListaX,ListaY,Rez,Osnova).