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)
	{
		GCD task = new GCD();
		//Test Case
		task.findGcd(15, 20);
		task.findGcd(24, 75);
		task.findGcd(45, 30);
		task.findGcd(21, 49);
		task.findGcd(16, 40);
		task.findGcd(-16, -40);
	}
}

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()
{
	GCD task = GCD();
	//Test Case
	task.findGcd(15, 20);
	task.findGcd(24, 75);
	task.findGcd(45, 30);
	task.findGcd(21, 49);
	task.findGcd(16, 40);
	task.findGcd(-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
// 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)
	{
		GCD task = new GCD();
		//Test Case
		task.findGcd(15, 20);
		task.findGcd(24, 75);
		task.findGcd(45, 30);
		task.findGcd(21, 49);
		task.findGcd(16, 40);
		task.findGcd(-16, -40);
	}
}

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()
{
	$task = new GCD();
	//Test Case
	$task->findGcd(15, 20);
	$task->findGcd(24, 75);
	$task->findGcd(45, 30);
	$task->findGcd(21, 49);
	$task->findGcd(16, 40);
	$task->findGcd(-16, -40);
}
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()
{
	var task = new GCD();
	//Test Case
	task.findGcd(15, 20);
	task.findGcd(24, 75);
	task.findGcd(45, 30);
	task.findGcd(21, 49);
	task.findGcd(16, 40);
	task.findGcd(-16, -40);
}
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() :
	task = GCD()
	# Test Case
	task.findGcd(15, 20)
	task.findGcd(24, 75)
	task.findGcd(45, 30)
	task.findGcd(21, 49)
	task.findGcd(16, 40)
	task.findGcd(-16, -40)

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() 
	task = GCD.new()
	# Test Case
	task.findGcd(15, 20)
	task.findGcd(24, 75)
	task.findGcd(45, 30)
	task.findGcd(21, 49)
	task.findGcd(16, 40)
	task.findGcd(-16, -40)
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
		task.findGcd(15, 20);
		task.findGcd(24, 75);
		task.findGcd(45, 30);
		task.findGcd(21, 49);
		task.findGcd(16, 40);
		task.findGcd(-16, -40);
	}
}

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()
{
	let task: GCD = GCD();
	//Test Case
	task.findGcd(15, 20);
	task.findGcd(24, 75);
	task.findGcd(45, 30);
	task.findGcd(21, 49);
	task.findGcd(16, 40);
	task.findGcd(-16, -40);
}
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
{
	var task: GCD = GCD();
	//Test Case
	task.findGcd(15, 20);
	task.findGcd(24, 75);
	task.findGcd(45, 30);
	task.findGcd(21, 49);
	task.findGcd(16, 40);
	task.findGcd(-16, -40);
}

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.

New Comment