Kako koristiti euklidski algoritam za pronalaženje najvećeg zajedničkog djelitelja (GCD)

Za ovu temu prvo morate znati o Najvećem zajedničkom djelitelju (GCD) i radu MORH-a.

Najveći zajednički djelitelj (GCD)

GCD od dvije ili više cijelih brojeva najveći je cijeli broj koji dijeli svaki od cijelih brojeva tako da je njihov ostatak jednak nuli.

Evo primjera:

GCD od 20, 30 = 10 (10 je najveći broj koji dijeli 20 i 30 s ostatkom 0)

GCD od 42, 120, 285 = 3 (3 je najveći broj koji dijeli 42, 120 i 285 s ostatkom 0)

"Mod" rad

Mod operacija daje vam ostatak kada se podijele dvije pozitivne cijele vrijednosti. Mi to zapisujemo na sljedeći način:

A mod B = R

To znači da dijeljenjem A s B dobivate ostatak R. To se razlikuje od vašeg postupka dijeljenja koji vam daje količnik.

Evo primjera:

7 mod 2 = 1 (Podjelom 7 s 2 dobiva se ostatak 1)

42 mod 7 = 0 (Dijeljenje 42 sa 7 daje ostatak 0)

Ako razumijete gornja dva pojma, lako ćete razumjeti euklidski algoritam.

Euklidov algoritam za najveći zajednički djelitelj (GCD)

Euklidov algoritam pronalazi GCD od 2 broja.

Ovaj ćete algoritam bolje razumjeti ako ga vidite na djelu. Pod pretpostavkom da želite izračunati GCD iz 1220. i 516., primijenimo Euklidov algoritam.

Pseudo kôd algoritma:

Korak 1: Neka a, bbudu dva broja

Korak 2: a mod b = R

Korak 3: Neka a = bib = R

Korak 4: Ponavljajte korake 2 i 3 dok ne a mod bbude veće od 0

Korak 5: GCD = b

Korak 6: Završi

Evo Javascript koda za izvođenje GCD-a:

function gcd(a, b) { var R; while ((a % b) > 0) { R = a % b; a = b; b = R; } return b; }

Evo Javascript koda za izvođenje GCD-a pomoću rekurzije:

function gcd(a, b) { if (b == 0) return a; else return gcd(b, (a % b)); }

Također možete koristiti Euklidov algoritam da biste pronašli GCD više od dva broja. Budući da je GCD asocijativan, vrijedi sljedeća operacija:  GCD(a,b,c) == GCD(GCD(a,b), c)

Izračunajte GCD prva dva broja, a zatim pronađite GCD rezultata i sljedeći broj. Primjer:GCD(203,91,77) == GCD(GCD(203,91),77) == GCD(7, 77) == 7

GCD nbrojeva možete pronaći na isti način.