Pentru acest subiect trebuie să știți mai întâi despre Greatest Common Divisor (GCD) și despre operațiunea MOD.

Cel mai mare divizor comun (GCD)

MCD de două sau mai multe numere întregi este cel mai mare număr întreg care împarte fiecare dintre numere întregi astfel încât restul lor să fie zero.

Exemplu-
GCD de 20, 30 = 10 (10 este cel mai mare număr care împarte 20 și 30 cu restul ca 0)
GCD de 42, 120, 285 = 3 (3 este cel mai mare număr care împarte 42, 120 și 285 cu restul ca 0)

Operațiunea „mod”

Operația mod vă oferă restul atunci când sunt împărțite două numere întregi pozitive. Îl scriem după cum urmează-
A mod B = R

Aceasta înseamnă că împărțirea A la B vă oferă restul R, acest lucru este diferit de operația de divizare care vă oferă coeficientul.

Exemplu-
7 mod 2 = 1 (Împărțirea 7 la 2 dă restul 1)
42 mod 7 = 0 (Împărțirea 42 la 7 dă restul 0)

Cu cele două concepte de mai sus înțelese, veți înțelege cu ușurință algoritmul euclidian.

Algoritmul euclidian pentru cel mai mare divizor comun (GCD)

Algoritmul euclidian găsește GCD de 2 numere.

Veți înțelege mai bine acest algoritm văzându-l în acțiune. Presupunând că doriți să calculați GCD de 1220 și 516, permiteți aplicarea algoritmului euclidian –

Presupunând că doriți să calculați GCD de 1220 și 516, permiteți aplicarea algoritmului euclidian –

Exemplu euclidian

Pseudo Codul Algoritmului-
Pasul 1: Lăsa a, b fie cele două numere
Pasul 2: a mod b = R
Pasul 3: Lăsa a = b și b = R
Pasul 4: Repetați pașii 2 și 3 până când a mod b este mai mare decât 0
Pasul 5: GCD = b
Pasul 6: Terminați

Cod JavaScript pentru a efectua GCD-

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

Cod JavaScript pentru a efectua GCD folosind Recursion-

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

Cod C pentru a efectua GCD folosind recursivitate

int gcd(int a, int b) 
{ 
    // Everything divides 0  
    if (a == 0) 
       return b; 
    if (b == 0) 
       return a; 
  
    // base case 
    if (a == b) 
        return a; 
  
    // a is greater 
    if (a > b) 
        return gcd(a-b, b); 
    return gcd(a, b-a); 
}

Cod C ++ pentru a efectua GCD-

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

Cod Python pentru a efectua GCD folosind Recursivitate

def gcd(a, b):
  if b == 0:
    return a:
  else:
    return gcd(b, (a % b))

Cod Java pentru a efectua GCD folosind Recursivitate

static int gcd(int a, int b)
{
  if(b == 0)
  {
    return a;
  }
  return gcd(b, a % b);
}

De asemenea, puteți utiliza algoritmul euclidian pentru a găsi GCD de mai mult de două numere. Deoarece, GCD este asociativ, următoarea operație este validă- GCD(a,b,c) == GCD(GCD(a,b), c)

Calculați GCD al primelor două numere, apoi găsiți GCD al rezultatului și următorul număr. Exemplu- GCD(203,91,77) == GCD(GCD(203,91),77) == GCD(7, 77) == 7

Puteți găsi GCD de n numerele în același mod.

Ce este algoritmul euclidian extins?

Aceasta este o extensie a algoritmului euclidian. De asemenea, calculează coeficienții x, y astfel încât

ax + by = mcd (a, b)

x și y sunt, de asemenea, cunoscuți ca coeficienți ai identității lui Bézout.

cod c pentru algoritmul euclidian extins

struct Triplet{
	int gcd;
	int x;
	int y;
};
Triplet gcdExtendedEuclid(int a,int b){
	//Base Case
	if(b==0){
		Triplet myAns;
		myAns.gcd = a;
		myAns.x = 1;
		myAns.y = 0;
		return myAns;

	}
	Triplet smallAns = gcdExtendedEuclid(b,a%b);
	//Extended euclid says

	Triplet myAns;
	myAns.gcd = smallAns.gcd;
	myAns.x  = smallAns.y;
	myAns.y = (smallAns.x - ((a/b)*(smallAns.y)));
	return myAns;	
}