Több szám lnko-ját hogy lehet kiszámolni?

Ennél egy sokkal hatásosabb módszer, az euklideszi algoritmus, ami a hétköznapi maradékos osztás algoritmusát használja fel.

Legegyszerűbben két szám legnagyobb közös osztóját úgy kapjuk meg, ha kivonjuk a kettő szám közül a nagyobbikból a kisebbet, mert a különbségnek is azonos az összes közös osztója. Így viszont csökkenő sorozatot kapunk, ami a két szám egyenlőségéhez, vagyis a legnagyobb közös osztóhoz tarthat csak. Ezt az ismételt összeadást nyilván egy maradékos osztással is elvégezhetjük, ekkor a sok kivonást elkerülendő a nagyobb számot osztjuk a kisebbel s helyére az osztás maradékát tesszük.

Elegánsabban fogalmazva a módszer a következő: elosztjuk a-t b-vel (a nagyobb számot a kisebbel - ha a két szám egyenlő, akkor ln. k. o.-juk a=b), majd az osztási maradékkal b-t, és így tovább, akkor az utolsó nem nulla maradék maga az lnko lesz. [2]

Példa:

lnko(84, 18) = ?

Ekkor elosztjuk 84-et 18-cal

a hányados 4, a maradék 12

elosztjuk 18-at 12-vel

a hányados 1, a maradék 6

elosztjuk 12-t 6-tal

a hányados 2, a maradék 0,

azaz itt megállt az algoritmus, nincs következő lépés, mivel 0-val nem lehet osztani. Tehát az utolsó nem nulla maradék a 6,

azaz lnko(84, 18) = 6.

Ha a és b közül egyik se nulla, akkor felhasználva a legkisebb közös többszörösüket, ami jelölésben az lkkt[a, b]:

Tulajdonságai [szerkesztés]

Az a és b számok bármely közös osztója osztója az lnko(a, b)-nek is.

lnko(a, b) = lnko(b, a)

lnko(a, a) = a

c·lnko(a, b) = lnko(c·a, c·b) (tetszőleges c számra)

lnko(a, b) = lnko(a+bc, b)

lnko(a, b) = a, akkor és csak akkor, ha a|b, azaz a osztója b-nek

ha lnko(a, b) = 1 és lnko(a, c) = 1, akkor lnko(a, b·c) = 1

ha a|b·c és lnko(a, b) = 1, akkor a|c

vagyis magyarul c nyelvben :

int LegNKO(int x, int y)

{

/* x és y legnagyobb közös osztójának meghatározása

* Euklidesz algoritmusával.

*/

int m;

while (y != 0) {

m = x % y;

x = y;

y = m;

}

return x;

}

Egy példa main() függvény több szám legnagyobb közös osztójához:

main()

{

int a, b;

printf("A program pozitív egész számok legnagyobb\\\\\\\\n");

printf("közös osztóját számítja.\\\\\\\\n");

printf("Kérem a számok sorozatát, amit 0 zár!\\\\\\\\n");

printf("? ");

scanf("%d%*[^\\\\\\\\n]", &a);

getchar();

while (1) { /* a hurok ciklus kezdete */

printf("? ");

scanf("%d%*[^\\\\\\\\n]", &b);

getchar();

if (b == 0) { /* első kijárat */

break;

}

a = LegNKO(a, b);

if (a == 1) { /* második kijárat */

break;

}

} /* a hurok ciklus vége */

printf(" A számok legnagyobb közös osztója: %d\\\\\\\\n",a);

}

természetesen a program elején: #include <stdio.h>