Este binecunoscut algoritmul de calcul al celui mai mare divizor comun (cmmdc) cu algoritmul lui Euclid prin impartiri repetate. Conform acestui algoritm cmmdc a doua numere naturale nenule $a$ si $b$ se calculeaza pastrand restul impartirii, si reluand impartirea cu vechiul impartitor si vechiul rest. Algoritmul se va termina cand restul impartirii devine zero. Cel mai mare divizor comun al celor doua numere $a$ si $b$ va fi ultimul impartitor.
Pentru calculul celui mai mare divizor comun al perechii $(16,22)$ se vor efectua succesiv impartirile:

table(example). |_. Deimpartit |_. Impartitor |_. Rest|_. Pas |

table. |_. Deimpartit |_. Impartitor |_. Rest|_. Pas |

| 16
| 22
| 16

| Pasul 5
|

Vom numi un “pas” o operatie de impartire ce intervine in calculului cmmdc. Se observa ca pentru determinarea cmmdc(16,22)=2 au fost necesari $5$ pasi.

Vom numi un pas o operatie de impartire ce intervine in calculului cmmdc. Se observa ca pentru determinarea cmmdc(16,22)=2 au fost necesari $5$ pasi.

h2. Cerinta

Cunoscand valoarea unui numar natural $n$, realizati un program care determina o pereche de numere naturale $(a,b)$ mai mici sau egale cu $n$, al caror cmmdc se obtine intr-un numar maxim de pasi. Daca exista mai multe perechi $(x,y)$ cu aceasta proprietate se va afisa cea minima. Spunem ca perechea $(a,b)$ este mai mica  decat $(x,y)$, daca $a<x$ sau $a=x$ si $b<y$.

Cunoscand valoarea unui numar natural $n$, realizati un program care determina o pereche de numere naturale $(a,b)$ mai mici sau egale cu $n$, al caror cmmdc se obtine intr-un numar maxim de pasi. Daca exista mai multe perechi $(x,y)$ cu aceasta proprietate se va afisa cea minima. Spunem ca perechea $(a,b)$ este mai mica decat $(x,y)$, daca $a<x$ sau $a=x$ si $b<y$.

h2. Date de intrare

Fisierul de intrare $euclid4.in$ contine un singur numar natural $n$

Fisierul de intrare $euclid4.in$ contine un singur numar natural {$n$}.

h2. Date de iesire

|
== include(page="template/taskfooter" task_id="euclid4") ==

3344