Posted on by Kalkicode
Code Algorithm

# Calculate GCD using euclid algorithm

The Euclidean algorithm is a method for finding the greatest common divisor (GCD) of two positive integers. Here are the steps:

1. Let a and b be the two positive integers for which we want to find the GCD.
2. Divide the larger number by the smaller number and take the remainder. Let r be the remainder.
3. If r is 0, then the smaller number is the GCD.
4. If r is not 0, then replace the larger number with the smaller number and the smaller number with the remainder (i.e., a = b and b = r) and go back to step 2.

Continue the above steps until r is 0. Then the GCD will be the last non-zero remainder.

Here's an example to find the GCD of 45 and 30 using the Euclidean algorithm:

Step 1: a = 45, b = 30 Step 2: 45 ÷ 30 = 1 remainder 15 Step 3: r ≠ 0, so replace a with b (a = 30) and b with r (b = 15) Step 4: 30 ÷ 15 = 2 remainder 0 Step 5: r = 0, so the GCD is the last non-zero remainder, which is 15.

Therefore, the GCD of 45 and 30 is 15.

Here given code implementation process.

``````// C Program
// Calculate GCD using euclid algorithm
#include <stdio.h>

// Calculate the GCD of given two numbers
int euclid(int a, int b)
{
int t = 0;
// Execute loop until b are not zero
while (b != 0)
{
// Get b value
t = b;
b = a % b;
// set new a
a = t;
}
return a;
}
// Handles the request to find GCD of two numbers
void find_gcd(int n1, int n2)
{
//Get GCD of two number
int result = euclid(n1, n2);
printf("\nNumbers (%d %d) : GCD : %d", n1, n2, result);
}
int main()
{
//Test Case
find_gcd(15, 20);
find_gcd(24, 75);
find_gcd(45, 30);
find_gcd(21, 49);
find_gcd(16, 40);
find_gcd(-16, -40);
return 0;
}``````

#### Output

``````Numbers (15 20) : GCD : 5
Numbers (24 75) : GCD : 3
Numbers (45 30) : GCD : 15
Numbers (21 49) : GCD : 7
Numbers (16 40) : GCD : 8
Numbers (-16 -40) : GCD : -8``````
``````/*
Java program
Calculate GCD using euclid algorithm
*/
public class GCD
{
// Calculate the GCD of given two numbers
public int euclid(int a, int b)
{
int t = 0;
// Execute loop until b are not zero
while (b != 0)
{
// Get b value
t = b;
b = a % b;
// set new a
a = t;
}
return a;
}
// Handles the request to find GCD of two numbers
public void findGcd(int n1, int n2)
{
//Get GCD of two number
int result = euclid(n1, n2);
System.out.print("\nNumbers (" + n1 + " " + n2 + ") : GCD : " + result);
}
public static void main(String[] args)
{
//Test Case
}
}``````

#### Output

``````Numbers (15 20) : GCD : 5
Numbers (24 75) : GCD : 3
Numbers (45 30) : GCD : 15
Numbers (21 49) : GCD : 7
Numbers (16 40) : GCD : 8
Numbers (-16 -40) : GCD : -8``````
``````// Include header file
#include <iostream>

using namespace std;
/*
C++ program
Calculate GCD using euclid algorithm
*/
class GCD
{
public:
// Calculate the GCD of given two numbers
int euclid(int a, int b)
{
int t = 0;
// Execute loop until b are not zero
while (b != 0)
{
// Get b value
t = b;
b = a % b;
// set new a
a = t;
}
return a;
}
// Handles the request to find GCD of two numbers
void findGcd(int n1, int n2)
{
//Get GCD of two number
int result = this->euclid(n1, n2);
cout << "\nNumbers (" << n1 << " " << n2 << ") : GCD : " << result;
}
};
int main()
{
//Test Case
return 0;
}``````

#### Output

``````Numbers (15 20) : GCD : 5
Numbers (24 75) : GCD : 3
Numbers (45 30) : GCD : 15
Numbers (21 49) : GCD : 7
Numbers (16 40) : GCD : 8
Numbers (-16 -40) : GCD : -8``````
``````// Include namespace system
using System;
/*
C# program
Calculate GCD using euclid algorithm
*/
public class GCD
{
// Calculate the GCD of given two numbers
public int euclid(int a, int b)
{
int t = 0;
// Execute loop until b are not zero
while (b != 0)
{
// Get b value
t = b;
b = a % b;
// set new a
a = t;
}
return a;
}
// Handles the request to find GCD of two numbers
public void findGcd(int n1, int n2)
{
//Get GCD of two number
int result = euclid(n1, n2);
Console.Write("\nNumbers (" + n1 + " " + n2 + ") : GCD : " + result);
}
public static void Main(String[] args)
{
//Test Case
}
}``````

#### Output

``````Numbers (15 20) : GCD : 5
Numbers (24 75) : GCD : 3
Numbers (45 30) : GCD : 15
Numbers (21 49) : GCD : 7
Numbers (16 40) : GCD : 8
Numbers (-16 -40) : GCD : -8``````
``````<?php
/*
Php program
Calculate GCD using euclid algorithm
*/
class GCD
{
// Calculate the GCD of given two numbers
public	function euclid(\$a, \$b)
{
\$t = 0;
// Execute loop until b are not zero
while (\$b != 0)
{
// Get b value
\$t = \$b;
\$b = \$a % \$b;
// set new a
\$a = \$t;
}
return \$a;
}
// Handles the request to find GCD of two numbers
public	function findGcd(\$n1, \$n2)
{
//Get GCD of two number
\$result = \$this->euclid(\$n1, \$n2);
echo "\nNumbers (". \$n1 ." ". \$n2 .") : GCD : ". \$result;
}
}

function main()
{
//Test Case
}
main();``````

#### Output

``````Numbers (15 20) : GCD : 5
Numbers (24 75) : GCD : 3
Numbers (45 30) : GCD : 15
Numbers (21 49) : GCD : 7
Numbers (16 40) : GCD : 8
Numbers (-16 -40) : GCD : -8``````
``````/*
Node Js program
Calculate GCD using euclid algorithm
*/
class GCD
{
// Calculate the GCD of given two numbers
euclid(a, b)
{
var t = 0;
// Execute loop until b are not zero
while (b != 0)
{
// Get b value
t = b;
b = a % b;
// set new a
a = t;
}
return a;
}
// Handles the request to find GCD of two numbers
findGcd(n1, n2)
{
//Get GCD of two number
var result = this.euclid(n1, n2);
process.stdout.write("\nNumbers (" + n1 + " " + n2 + ") : GCD : " + result);
}
}

function main()
{
//Test Case
}
main();``````

#### Output

``````Numbers (15 20) : GCD : 5
Numbers (24 75) : GCD : 3
Numbers (45 30) : GCD : 15
Numbers (21 49) : GCD : 7
Numbers (16 40) : GCD : 8
Numbers (-16 -40) : GCD : -8``````
``````#   Python 3 program
#   Calculate GCD using euclid algorithm

class GCD :
#  Calculate the GCD of given two numbers
def euclid(self, a, b) :
t = 0
#  Execute loop until b are not zero
while (b != 0) :
#  Get b value
t = b
b = a % b
#  set new a
a = t

return a

#  Handles the request to find GCD of two numbers
def findGcd(self, n1, n2) :
# Get GCD of two number
result = self.euclid(n1, n2)
print("\nNumbers (", n1 ," ", n2 ,"): GCD : ", result, end = "")

def main() :
# Test Case

if __name__ == "__main__": main()``````

#### Output

``````Numbers ( 15   20 ): GCD :  5
Numbers ( 24   75 ): GCD :  3
Numbers ( 45   30 ): GCD :  15
Numbers ( 21   49 ): GCD :  7
Numbers ( 16   40 ): GCD :  8
Numbers ( -16   -40 ): GCD :  -8``````
``````#   Ruby program
#   Calculate GCD using euclid algorithm

class GCD
#  Calculate the GCD of given two numbers
def euclid(a, b)
t = 0
#  Execute loop until b are not zero
while (b != 0)
#  Get b value
t = b
b = a % b
#  set new a
a = t
end

return a
end

#  Handles the request to find GCD of two numbers
def findGcd(n1, n2)
# Get GCD of two number
result = self.euclid(n1, n2)
print("\nNumbers (", n1 ," ", n2 ,") : GCD : ", result)
end

end

def main()
# Test Case
end

main()``````

#### Output

``````Numbers (15 20) : GCD : 5
Numbers (24 75) : GCD : 3
Numbers (45 30) : GCD : 15
Numbers (21 49) : GCD : 7
Numbers (16 40) : GCD : 8
Numbers (-16 -40) : GCD : -8``````
``````/*
Scala program
Calculate GCD using euclid algorithm
*/
class GCD
{
// Calculate the GCD of given two numbers
def euclid(x: Int, y: Int): Int = {
var a =  x;
var b =  y;
var t: Int = 0;
// Execute loop until b are not zero
while (b != 0)
{
// Get b value
t = b;
b = a % b;
// set new a
a = t;
}
return a;
}
// Handles the request to find GCD of two numbers
def findGcd(n1: Int, n2: Int): Unit = {
//Get GCD of two number
var result: Int = this.euclid(n1, n2);
print("\nNumbers (" + n1 + " " + n2 + ") : GCD : " + result);
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: GCD = new GCD();
//Test Case
}
}``````

#### Output

``````Numbers (15 20) : GCD : 5
Numbers (24 75) : GCD : 3
Numbers (45 30) : GCD : 15
Numbers (21 49) : GCD : 7
Numbers (16 40) : GCD : 8
Numbers (-16 -40) : GCD : -8``````
``````/*
Swift 4 program
Calculate GCD using euclid algorithm
*/
class GCD
{
// Calculate the GCD of given two numbers
func euclid(_ x: Int, _ y: Int)->Int
{
var a: Int = x;
var b: Int = y;
var t: Int = 0;
// Execute loop until b are not zero
while (b  != 0)
{
// Get b value
t = b;
b = a % b;
// set new a
a = t;
}
return a;
}
// Handles the request to find GCD of two numbers
func findGcd(_ n1: Int, _ n2: Int)
{
//Get GCD of two number
let result: Int = self.euclid(n1, n2);
print("\nNumbers (", n1 ,"", n2 ,") : GCD : ", result, terminator: "");
}
}
func main()
{
//Test Case
}
main();``````

#### Output

``````Numbers ( 15  20 ) : GCD :  5
Numbers ( 24  75 ) : GCD :  3
Numbers ( 45  30 ) : GCD :  15
Numbers ( 21  49 ) : GCD :  7
Numbers ( 16  40 ) : GCD :  8
Numbers ( -16  -40 ) : GCD :  -8``````
``````/*
Kotlin program
Calculate GCD using euclid algorithm
*/
class GCD
{
// Calculate the GCD of given two numbers
fun euclid(x: Int, y: Int): Int
{
var a: Int = x;
var b: Int = y;
var t: Int ;
// Execute loop until b are not zero
while (b != 0)
{
// Get b value
t = b;
b = a % b;
// set new a
a = t;
}
return a;
}
// Handles the request to find GCD of two numbers
fun findGcd(n1: Int, n2: Int): Unit
{
//Get GCD of two number
var result: Int = this.euclid(n1, n2);
print("\nNumbers (" + n1 + " " + n2 + ") : GCD : " + result);
}
}
fun main(args: Array < String > ): Unit
{
//Test Case
}``````

#### Output

``````Numbers (15 20) : GCD : 5
Numbers (24 75) : GCD : 3
Numbers (45 30) : GCD : 15
Numbers (21 49) : GCD : 7
Numbers (16 40) : GCD : 8
Numbers (-16 -40) : GCD : -8``````

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

Categories
Relative Post