# Eukleidův algoritmus pro nalezení NSD dvou čísel

# vstup dat
m = int(input('Zadej první přirozené číslo: '))
n = int(input('Zadej druhé přirozené číslo: '))

# krok 1: zajistíme, že n není větší z čísel
if m < n:
    m, n = n, m # prohození čísel

# krok 2: provádíme cyklus, dokud není n nulové
while n != 0:
    r = m % n # krok 2a: zbytek po dělení
    m = n # krok 2b: nová hodnota m
    n = r # krok 2c: nová hodnota n

# krok 3: dokončeno, vypíšeme výsledek
print('NSD zadaných čísel je', m)