/*======================================================
**Implementacja algorytmu Euklidesa
**Narzew
**18.10.2013
**dla portalu algorytm.org
======================================================*/

#include <cstdlib>
#include <iostream>
#include <cstdio>

using namespace std;

/*======================================================
**oblicz_nwd(a,b,p)
**Największy wspólny dzielnik
**a => liczba A
**b => liczba B
**c => czy wyświetlać obliczenia ? 0 - nie, 1 - tak
======================================================*/

int oblicz_nwd(int a,int b, bool print){
	int count = 0;
	if (a == b){
		if (print == true){ cout<< "Wynik : "<<a<<"\n"; }
		return a;
	}
	while (a != b){
		count++;
		if (a < b){
			b = b-a;
			if (print == true){ printf("#%d: A: %d B: %d\n",count,a,b); }
		} else {
			a = a-b;
			if (print == true){ printf("#%d: A: %d B: %d\n",count,a,b); }
		}
	}
	if (print==true){ cout << "NWD: "<<a<<"\n"; }
	return a;
}

/*======================================================
**Main
======================================================*/

int main(){
	int a,b;
	cout << "Obliczanie NWD by Narzew\n"<<
	"18.10.2013\n\n";
	
	cout << "Podaj pierwsza liczbe : ";
	cin >> a;
	cout << "Podaj druga liczbe : ";
	cin >> b;
	oblicz_nwd(a,b,true);

	return 0;
}