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.
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;> }> |
>
alisa manyonok
>
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>>>string split bashIeșireGCD(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 x1și y1. x și y sunt actualizate folosind expresiile de mai jos.
Practică recomandată Algoritmul euclidian extins Încercați!ax + by = mcd(a, b)
mcd(a, b) = mcd(b%a, a)
gcd(b%a, a) = (b%a)x1+ este1
ax + de = (b%a)x1+ este1
ax + by = (b – [b/a] * a)x1+ este1
ax + by = a(y1– [b/a] * x1) + bx1Comparând LHS și RHS,
x = y1– ?b/a? * X1
y = x1Mai 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
programare dinamică
# 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 x1și y1sunt rezultate pentru intrările b%a și a
(b%a).x1+ a.a1= 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).x1+ a.a1= gcd
Ecuația de mai sus poate fi scrisă și ca mai jos
b.x1+ a.(și1– (?b/a?).x1) = mcd —(2)
După compararea coeficienților lui „a” și „b” din (1) și
(2), obținem următoarele,
x = y1– ?b/a? * X1
y = x1Cum 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.