Készítsünk programot bármilyen nyelven, amely meghatározza két pozitív egész szám legnagyobb közös osztóját euklidészi algoritmussal! A maradékos osztás (modulus képzés: mod) alapműveletként használható, azt nem kell beprogramozni.
Segítségek a feladat megoldásához:
Maradékos osztás: a és b maradékosan elosztva azt a számot adja vissza, amely a és b elosztásánál a maradék. Pl. 18 osztva maradékosan 5-tel eredménye 3 (azaz 18 mod 5 = 3)
Euklidészi algoritmus: A két számot osszuk el egymással maradékosan. Ha a maradék 0, akkor nyilván az osztás osztója a legnagyobb közös osztó. Ha nem 0, akkor mindig az előző osztót osszuk el az előző maradékkal. Matematikailag bizonyítható, hogy előbb-utóbb 0-t fogunk kapni maradékul. Az utolsó nem 0 maradék a legnagyobb közös osztó, ez a végeredmény.
Megoldás forrás file: