Algorytm Euklidesa (NWD)

Algorytm Euklidesa to klasyczna metoda obliczania największego wspólnego dzielnika (NWD) dwóch liczb całkowitych. NWD dwóch liczb to największa liczba całkowita, która dzieli obie z tych liczb bez reszty.

Algorytm Euklidesa jest bardzo efektywny i działa ze złożonością logarytmiczną.

def NWD(a, b):
	while b > 0:
		reszta = a % b
		a = b
		b = reszta
	return a