ALGORITMI EUCLIDIENI (DE BAZĂ ȘI EXTINSE) - TECHCODEVIEW.COM

Algoritmul euclidian este o modalitate de a găsi cel mai mare divizor comun a două numere întregi pozitive. MCD a două numere este cel mai mare număr care le împarte pe ambele. O modalitate simplă de a găsi GCD este factorizarea ambelor numere și înmulțirea factorilor primi comuni.

GCD

Algoritmul euclidian de bază pentru GCD:

Algoritmul se bazează pe faptele de mai jos.

Dacă scădem un număr mai mic dintr-unul mai mare (reducem un număr mai mare), GCD nu se schimbă. Deci, dacă continuăm să scădem în mod repetat pe cel mai mare dintre doi, ajungem cu GCD.
Acum, în loc de scădere, dacă împărțim numărul mai mic, algoritmul se oprește când găsim restul 0.

Mai jos este o funcție recursivă pentru a evalua gcd folosind algoritmul lui Euclid:

C

// C program to demonstrate Basic Euclidean Algorithm> #include> // Function to return gcd of a and b> int> gcd(> int> a,> int> b)> {> > if> (a == 0)> > return> b;> > return> gcd(b % a, a);> }> // Driver code> int> main()> {> > int> a = 10, b = 15;> > > // Function call> > printf> (>

'GCD(%d, %d) = %d
'>

, a, b, gcd(a, b));> > a = 35, b = 10;> > printf> (>

'GCD(%d, %d) = %d
'>

, a, b, gcd(a, b));> > a = 31, b = 2;> > printf> (>

'GCD(%d, %d) = %d
'>

, a, b, gcd(a, b));> > return> 0;> }>

CPP

// C++ program to demonstrate> // Basic Euclidean Algorithm> #include> using> namespace> std;> // Function to return> // gcd of a and b> int> gcd(> int> a,> int> b)> {> > if> (a == 0)> > return> b;> > return> gcd(b % a, a);> }> // Driver Code> int> main()> {> > int> a = 10, b = 15;> > > // Function call> > cout < <> 'GCD('> < < a < <> ', '> < < b < <> ') = '> < < gcd(a, b)> > < < endl;> > a = 35, b = 10;> > cout < <> 'GCD('> < < a < <> ', '> < < b < <> ') = '> < < gcd(a, b)> > < < endl;> > a = 31, b = 2;> > cout < <> 'GCD('> < < a < <> ', '> < < b < <> ') = '> < < gcd(a, b)> > < < endl;> > return> 0;> }>

Java

// Java program to demonstrate Basic Euclidean Algorithm> import> java.lang.*;> import> java.util.*;> class> GFG {> > // extended Euclidean Algorithm> > public> static> int> gcd(> int> a,> int> b)> > {> > if> (a ==> 0> )> > return> b;> > return> gcd(b % a, a);> > }> > // Driver code> > public> static> void> main(String[] args)> > {> > int> a => 10> , b => 15> , g;> > > // Function call> > g = gcd(a, b);> > System.out.println(> 'GCD('> + a +> ' , '> + b> > +> ') = '> + g);> > a => 35> ;> > b => 10> ;> > g = gcd(a, b);> > System.out.println(> 'GCD('> + a +> ' , '> + b> > +> ') = '> + g);> > a => 31> ;> > b => 2> ;> > g = gcd(a, b);> > System.out.println(> 'GCD('> + a +> ' , '> + b> > +> ') = '> + g);> > }> }> // Code Contributed by Mohit Gupta_OMG>

Python3

# Python3 program to demonstrate Basic Euclidean Algorithm> # Function to return gcd of a and b> def> gcd(a, b):> > if> a> => => 0> :> > return> b> > return> gcd(b> %> a, a)> # Driver code> if> __name__> => => '__main__'> :> > a> => 10> > b> => 15> > print> (> 'gcd('> , a,> ','> , b,> ') = '> , gcd(a, b))> > a> => 35> > b> => 10> > print> (> 'gcd('> , a,> ','> , b,> ') = '> , gcd(a, b))> > a> => 31> > b> => 2> > print> (> 'gcd('> , a,> ','> , b,> ') = '> , gcd(a, b))> # Code Contributed By Mohit Gupta_OMG>

C#

// C# program to demonstrate Basic Euclidean Algorithm> using> System;> class> GFG {> > public> static> int> gcd(> int> a,> int> b)> > {> > if> (a == 0)> > return> b;> > return> gcd(b % a, a);> > }> > // Driver Code> > static> public> void> Main()> > {> > int> a = 10, b = 15, g;> > g = gcd(a, b);> > Console.WriteLine(> 'GCD('> + a +> ' , '> + b> > +> ') = '> + g);> > a = 35;> > b = 10;> > g = gcd(a, b);> > Console.WriteLine(> 'GCD('> + a +> ' , '> + b> > +> ') = '> + g);> > a = 31;> > b = 2;> > g = gcd(a, b);> > Console.WriteLine(> 'GCD('> + a +> ' , '> + b> > +> ') = '> + g);> > }> }> // This code is contributed by ajit>

PHP

// php program to demonstrate Basic Euclidean Algorithm>

 // PHP program to demonstrate // Basic Euclidean Algorithm // Function to return // gcd of a and b function gcd($a, $b) {  if ($a == 0)  return $b;  return gcd($b % $a, $a); } // Driver Code $a = 10; $b = 15; // Function call echo 'GCD(',$a,',' , $b,') = ',   gcd($a, $b); echo '
'; $a = 35; $b = 10; echo 'GCD(',$a ,',',$b,') = ',   gcd($a, $b); echo '
'; $a = 31; $b = 2; echo 'GCD(',$a ,',', $b,') = ',   gcd($a, $b); // This code is contributed by m_kit ?>>>>

>    
      
      
       
   
       
       
     
     
   
          // JavaScript program to demonstrate>   // Basic Euclidean Algorithm>   // Function to return>   // gcd of a and b>   function>   gcd( a, b)>   {>   >  if>   (a == 0)>   >  return>   b;>   >  return>   gcd(b % a, a);>   }>   // Driver Code>   >  let a = 10, b = 15;>   >  document.write(>  'GCD('>   + a +>  ', '>   >  + b +>  ') = '>   + gcd(a, b) +>  ' '>  );>   >   >  a = 35, b = 10;>   >  document.write(>  'GCD('>   + a +>  ', '>   >  + b +>  ') = '>   + gcd(a, b) +>  ' '>  );>   >   >  a = 31, b = 2;>   >  document.write(>  'GCD('>   + a +>  ', '>   >  + b +>  ') = '>   + gcd(a, b) +>  ' '>  );>   // This code contributed by aashish1995>     
  
  
   
      
    
      
    
  Ieșire    
  GCD(10, 15) = 5 GCD(35, 10) = 5 GCD(31, 2) = 1 
    Complexitatea timpului: O(Log min(a, b)) 
  Spațiu auxiliar: O(Log (min(a,b)) 
    Algoritmul euclidian extins:   
    Algoritmul euclidian extins găsește și coeficienți întregi x și y astfel încât: ax + by = gcd(a, b) 
  
    Exemple:   
      Intrare: a = 30, b = 20 
  Ieșire: mcd = 10, x = 1, y = -1 
(Rețineți că 30*1 + 20*(-1) = 10) 
    Intrare: a = 35, b = 15 
  Ieșire: mcd = 5, x = 1, y = -2 
(Rețineți că 35*1 + 15*(-2) = 5) 
  
  Algoritmul euclidian extins actualizează rezultatele gcd(a, b) folosind rezultatele calculate prin apelul recursiv gcd(b%a, a). Fie valorile lui x și y calculate prin apelul recursiv să fie x ₁și y ₁. x și y sunt actualizate folosind expresiile de mai jos. 
    ax + by = mcd(a, b) 
mcd(a, b) = mcd(b%a, a) 
gcd(b%a, a) = (b%a)x ₁+ este ₁  
ax + de = (b%a)x ₁+ este ₁  
ax + by = (b – [b/a] * a)x ₁+ este ₁  
ax + by = a(y ₁– [b/a] * x ₁) + bx ₁ 
  Comparând LHS și RHS, 
x = y ₁– ?b/a? * X ₁  
y = x ₁ 
  
Practică recomandată Algoritmul euclidian extins Încercați! Mai jos este o implementare a abordării de mai sus: 
  C++ 
      
       
   
       
       
     
     
   
          // C++ program to demonstrate working of>   // extended Euclidean Algorithm>   #include>   using>   namespace>   std;>   // Function for extended Euclidean Algorithm>   int>   gcdExtended(>  int>   a,>  int>   b,>  int>   *x,>  int>   *y)>   {>   >  // Base Case>   >  if>   (a == 0)>   >  {>   >  *x = 0;>   >  *y = 1;>   >  return>   b;>   >  }>   >  int>   x1, y1;>  // To store results of recursive call>   >  int>   gcd = gcdExtended(b%a, a, &x1, &y1);>   >  // Update x and y using results of>   >  // recursive call>   >  *x = y1 - (b/a) * x1;>   >  *y = x1;>   >  return>   gcd;>   }>   // Driver Code>   int>   main()>   {>   >  int>   x, y, a = 35, b = 15;>   >  int>   g = gcdExtended(a, b, &x, &y);>   >  cout  < <>  'GCD('>    < < a  < <>  ', '>    < < b>   >   < <>  ') = '>    < < g  < < endl;>   >  return>   0;>   }>     
  
  
   
      
    
      
    
  C 
      
       
   
       
       
     
     
   
          // C program to demonstrate working of extended>   // Euclidean Algorithm>   #include>   // C function for extended Euclidean Algorithm>   int>   gcdExtended(>  int>   a,>  int>   b,>  int>   *x,>  int>   *y)>   {>   >  // Base Case>   >  if>   (a == 0)>   >  {>   >  *x = 0;>   >  *y = 1;>   >  return>   b;>   >  }>   >  int>   x1, y1;>  // To store results of recursive call>   >  int>   gcd = gcdExtended(b%a, a, &x1, &y1);>   >  // Update x and y using results of recursive>   >  // call>   >  *x = y1 - (b/a) * x1;>   >  *y = x1;>   >  return>   gcd;>   }>   // Driver Program>   int>   main()>   {>   >  int>   x, y;>   >  int>   a = 35, b = 15;>   >  int>   g = gcdExtended(a, b, &x, &y);>   >  printf>  (>  'gcd(%d, %d) = %d'>  , a, b, g);>   >  return>   0;>   }>     
  
  
   
      
    
      
    
  Java 
      
       
   
       
       
     
     
   
          // Java program to demonstrate working of extended>   // Euclidean Algorithm>   import>   java.lang.*;>   import>   java.util.*;>   class>   GFG {>   >  // extended Euclidean Algorithm>   >  public>   static>   int>   gcdExtended(>  int>   a,>  int>   b,>  int>   x,>   >  int>   y)>   >  {>   >  // Base Case>   >  if>   (a ==>  0>  ) {>   >  x =>  0>  ;>   >  y =>  1>  ;>   >  return>   b;>   >  }>   >  int>   x1 =>  1>  ,>   >  y1 =>  1>  ;>  // To store results of recursive call>   >  int>   gcd = gcdExtended(b % a, a, x1, y1);>   >  // Update x and y using results of recursive>   >  // call>   >  x = y1 - (b / a) * x1;>   >  y = x1;>   >  return>   gcd;>   >  }>   >  // Driver Program>   >  public>   static>   void>   main(String[] args)>   >  {>   >  int>   x =>  1>  , y =>  1>  ;>   >  int>   a =>  35>  , b =>  15>  ;>   >  int>   g = gcdExtended(a, b, x, y);>   >  System.out.print(>  'gcd('>   + a +>  ' , '>   + b>   >  +>  ') = '>   + g);>   >  }>   }>     
  
  
   
      
    
      
    
  Python3 
      
       
   
       
       
     
     
   
          # Python program to demonstrate working of extended>   # Euclidean Algorithm>   # function for extended Euclidean Algorithm>   def>   gcdExtended(a, b):>   >  # Base Case>   >  if>   a>  =>  =>   0>  :>   >  return>   b,>  0>  ,>  1>   >  gcd, x1, y1>  =>   gcdExtended(b>  %>   a, a)>   >  # Update x and y using results of recursive>   >  # call>   >  x>  =>   y1>  ->   (b>  />  />  a)>  *>   x1>   >  y>  =>   x1>   >  return>   gcd, x, y>   # Driver code>   a, b>  =>   35>  ,>  15>   g, x, y>  =>   gcdExtended(a, b)>   print>  (>  'gcd('>  , a,>  ','>  , b,>  ') = '>  , g)>     
  
  
   
      
    
      
    
  C# 
      
       
   
       
       
     
     
   
          // C# program to demonstrate working>   // of extended Euclidean Algorithm>   using>   System;>   class>   GFG>   {>   >   >  // extended Euclidean Algorithm>   >  public>   static>   int>   gcdExtended(>  int>   a,>  int>   b,>   >  int>   x,>  int>   y)>   >  {>   >  // Base Case>   >  if>   (a == 0)>   >  {>   >  x = 0;>   >  y = 1;>   >  return>   b;>   >  }>   >  // To store results of>   >  // recursive call>   >  int>   x1 = 1, y1 = 1;>   >  int>   gcd = gcdExtended(b % a, a, x1, y1);>   >  // Update x and y using>   >  // results of recursive call>   >  x = y1 - (b / a) * x1;>   >  y = x1;>   >  return>   gcd;>   >  }>   >   >  // Driver Code>   >  static>   public>   void>   Main ()>   >  {>   >  int>   x = 1, y = 1;>   >  int>   a = 35, b = 15;>   >  int>   g = gcdExtended(a, b, x, y);>   >  Console.WriteLine(>  'gcd('>   + a +>  ' , '>   +>   >  b +>  ') = '>   + g);>   >  }>   }>     
  
  
   
      
    
      
    
  PHP 
      
       
   
       
       
     
     
   
           // PHP program to demonstrate  // working of extended  // Euclidean Algorithm // PHP function for  // extended Euclidean  // Algorithm function gcdExtended($a, $b,   $x, $y) {  // Base Case  if ($a == 0)  {  $x = 0;  $y = 1;  return $b;  }  // To store results   // of recursive call  $gcd = gcdExtended($b % $a,   $a, $x, $y);  // Update x and y using  // results of recursive  // call  $x = $y - floor($b / $a) * $x;  $y = $x;  return $gcd; } // Driver Code $x = 0; $y = 0; $a = 35; $b = 15; $g = gcdExtended($a, $b, $x, $y); echo 'gcd(',$a; echo ', ' , $b, ')'; echo ' = ' , $g; ?>>>>    
  
  
   
      
  >    
      
      
       
   
       
       
     
     
   
          >   // Javascript program to demonstrate>   // working of extended>   // Euclidean Algorithm>   // Javascript function for>   // extended Euclidean>   // Algorithm>   function>   gcdExtended(a, b,>   >  x, y)>   {>   >  // Base Case>   >  if>   (a == 0)>   >  {>   >  x = 0;>   >  y = 1;>   >  return>   b;>   >  }>   >  // To store results>   >  // of recursive call>   >  let gcd = gcdExtended(b % a,>   >  a, x, y);>   >  // Update x and y using>   >  // results of recursive>   >  // call>   >  x = y - (b / a) * x;>   >  y = x;>   >  return>   gcd;>   }>   // Driver Code>   let x = 0;>   let y = 0;>   let a = 35;>   let b = 15;>   let g = gcdExtended(a, b, x, y);>   document.write(>  'gcd('>   + a);>   document.write(>  ', '>   + b +>  ')'>  );>   document.write(>  ' = '>   + g);>   >     
  
  
   
      
    
      
    
    Ieșire:   
  gcd(35, 15) = 5 
    Complexitatea timpului: O(log N) 
  Spațiu auxiliar: O(log N) 
    Cum funcționează algoritmul extins?   
    După cum sa văzut mai sus, x și y sunt rezultate pentru intrările a și b, 
  a.x + b.y = mcd —-(1) 
  Și x ₁și y ₁sunt rezultate pentru intrările b%a și a 
  (b%a).x ₁+ a.a ₁= gcd 
  Când punem b%a = (b – (?b/a?).a) mai sus, 
primim urmări. Rețineți că ?b/a? este etajul (b/a) 
  (b – (?b/a?).a).x ₁+ a.a ₁= gcd 
  Ecuația de mai sus poate fi scrisă și ca mai jos 
  b.x ₁+ a.(și ₁– (?b/a?).x ₁) = mcd —(2) 
  După compararea coeficienților lui „a” și „b” din (1) și 
(2), obținem următoarele, 
x = y ₁– ?b/a? * X ₁  
y = x ₁ 
  
    Cum este util algoritmul extins?   
  Algoritmul euclidian extins este deosebit de util atunci când a și b sunt coprime (sau mcd este 1). Deoarece x este inversul multiplicativ modular al lui a modulo b și y este inversul multiplicativ modular al lui b modulo a. În special, calculul inversului multiplicativ modular este un pas esențial în metoda de criptare a cheii publice RSA.