ユークリッドアルゴリズム (基本および拡張) - TECHCODEVIEW.COM

ユークリッドアルゴリズムは、2 つの正の整数の最大公約数を見つける方法です。 2 つの数値の GCD は、両方を除算する最大の数です。 GCD を求める簡単な方法は、両方の数値を因数分解し、共通の素因数を乗算することです。

GCD

GCD の基本的なユークリッドアルゴリズム:

このアルゴリズムは以下の事実に基づいています。

大きい数から小さい数を引いても (大きい数を減らしても)、GCD は変わりません。したがって、2 のうち大きい方を繰り返し減算し続けると、最終的に GCD が得られます。
減算の代わりに、小さい方の数値を除算すると、余りが 0 になった時点でアルゴリズムが停止します。

以下は、Euclid のアルゴリズムを使用して gcd を評価する再帰関数です。

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 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

// 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>

出力

GCD(10, 15) = 5 GCD(35, 10) = 5 GCD(31, 2) = 1

時間計算量: O(ログ最小(a, b))
補助スペース: O(Log (min(a,b))

拡張ユークリッドアルゴリズム:

拡張ユークリッドアルゴリズムでは、次のような整数係数 x および y も検索されます。 ax + by = gcd(a, b)

例:

入力： a = 30、b = 20
出力： gcd = 10、x = 1、y = -1
(30*1 + 20*(-1) = 10 であることに注意してください)

入力： a = 35、b = 15
出力： gcd = 5、x = 1、y = -2
(35*1 + 15*(-2) = 5 であることに注意してください)

拡張ユークリッドアルゴリズムは、再帰呼び出し gcd(b%a, a) によって計算された結果を使用して、gcd(a, b) の結果を更新します。再帰呼び出しで計算されたxとyの値をxとする ₁そしてy ₁。 x と y は以下の式を使用して更新されます。

ax + by = gcd(a, b)
gcd(a, b) = gcd(b%a, a)
gcd(b%a, a) = (b%a)x ₁+は ₁
ax + by = (b%a)x ₁+は ₁
ax + by = (b – [b/a] * a)x ₁+は ₁
ax + by = a(y ₁– [b/a] * x ₁) + bx ₁

左側と右側を比較すると、
x = y ₁– ?b/a? * バツ ₁
y = x ₁

推奨演習拡張ユークリッドアルゴリズム試してみましょう!

以下は上記のアプローチの実装です。

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 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

> // 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);> >

出力:

gcd(35, 15) = 5

時間計算量: O(log N)
補助スペース: O(log N)

拡張アルゴリズムはどのように機能するのでしょうか?

上で見たように、x と y は入力 a と b の結果です。

a.x + b.y = gcd —-(1)

そして× ₁そしてy ₁入力 b%a および a の結果です

(b%a).x ₁+ああ ₁= gcd

上記に b%a = (b – (?b/a?).a) を代入すると、
フォローを取得します。 ?b/a? に注意してください。床(b/a)です

(b – (?b/a?).a).x ₁+ああ ₁= gcd

上式は次のように書くこともできます

b.x ₁+ a.(そして ₁– (?b/a?).x ₁) = gcd —(2)

(1)の「a」と「b」の係数を比較した後、
(2) を実行すると、次のようになります。
x = y ₁– ?b/a? * バツ ₁
y = x ₁