Vytvořte program, který zjistí největší společný dělitel (NSD) dvou čísel. Čísla od uživatele načtěte "na jednom řádku" 
(pomocí scanf, který načítá do dvou proměnných).

Pokud byste hledali nejmenší společný dělitel čísel ručně, pravděpodobně byste obě čísla rozložili na prvočísla.
Obecně je však rozklad na prvočísla složitý problém - můžete si to zkusit např. pro číslo 3869, pravděpodobně vám to
chvíli zabere. Proto je hledání NSD pomocí rozkladu na prvočísla zdlouhavé a hlavně velice neefektivní. Naštěstí
existují jednodušší způsoby. Jedním z nich je tzv. Euklidův algoritmus. První zmínka je z roku 300 př.n.l., Euklides
ho publikoval, ale autor je neznámý - je vidět, že efektivita výpočtu není něco, co řešíme jenom v souvislosti s počítači.
Bližší informace v případě zájmu naleznete zde:
http://cs.wikipedia.org/wiki/Eukleid%C5%AFv_algoritmus 
http://www.algoritmy.net/article/44/Eukliduv-algoritmus
http://www.itnetwork.cz/algoritmus-vypocet-nejvetsiho-spolecneho-delitele-eukliduv-algoritmus

Můžete zkusit naprogramovat verzi s modulem na odkazech, vzorové řešení ale využívá alternativu, která využívá jenom 
odčítání.
Ta funguje tak, že v každém kroku výpočtu porovnáme dvě čísla (např. a, b). To číslo, které je větší (např. a), 
přepíšeme rozdílem dvou původních čísel (např. a = a - b) a výpočet opakujeme v dalším kroku. Znovu porovnáme čísla
a znovu odčítáme. Ukázka:
1. krok:
a == 39
b == 9
a > b => a = 39 - 9 = 30

2. krok:
a == 30
b == 9
a > b => a = 30 - 9 = 21

3. krok:
a == 21
b == 9
a > b => a = 21 - 9 = 12

4. krok:
a == 12
b == 9
a > b => a = 12 - 9 = 3

5. krok: Změna, a je poprvé menší než b
a == 3
b == 9
a < b => b = 9 - 3 = 6

6. krok:
a == 3
b == 6
a < b => b = 6 - 3 = 3

7. krok: nalezení výsledku - už nemá smysl nic odčítat
a == 3
b == 3
a == b => NSD nalezen


----------------------------------------------------------------------------------------------

Následuje vysvětlení algoritmu.


Obě dvě varianty jsou velice jednoduché na naprogramování, ale už o něco obtížnější na pochopení (a vysvětlení), 
proč to vlastně funguje. Pokusíme se zde vysvětlit variantu s odčítáním, varianta s modulem je vysvětlena na odkazu 
na algoritmy.net.

Myšlenkou algoritmu je to, že sice měnim hodnotu čísel, pro které NSD hledám, ale hodnota jejich NSD se těmito změnami nemění.
Proč tomu tak je?

Každé z čísel si můžeme představit jako nějaký násobek NSD, pro výše uvedený příklad tedy 39 = 3 x 13; 9 = 3 x 3.
To můžeme znázornit "graficky" (X = 3, hodnota čísla = počet X x 3):

krok 1:
a (39): XXXXXXXXXXXXX
b (9):  XXX

krok 2: Pokud tato čísla od sebe odečteme, odečítáme také násbek tří. Takže NSD se nemění:
a (30): XXXXXXXXXX
b (9):  XXX
 
krok 3:
a (21): XXXXXXX
b (9):  XXX

krok 4:
a (12): XXXX
b (9):  XXX

krok 5:
a (3): X
b (9): XXX

krok 6:
a (3): X
b (6): XX

krok 7:
a (3): X
b (3): X


Z "ilustrace" by mělo být zřejmé, že vždy odečítám nějaký násobek NSD, původní NSD se tedy touto operací nezmění.
Konkrétní hodnotu "X" samozřejmě zjistíme až v posledním kroku. algoritmus na začátku ani neví, kolik "X" se mu do 
čísla vejde (protože hodnotu NSD nezná). Může si ale být jistý, že nějaké takové X existuje (v nejhorším případě to bude
1) a že pokud bude pracovat tímto postupem, nakonec se k hodnotě X dobere.

P.S.: 3869 = 53 x 73