Euclidean algorithm for GCD of two numbers
The idea of this algorithm is, the GCD of two numbers doesn’t change if the smaller number is subtracted from the bigger number. This is the Euclidean algorithm by subtraction. It is a process of repeat subtraction, carrying the result forward each time until the result is equal to any one number being subtracted.
Pseudo-code:
gcd(a, b):
if a = b:
return a
if a > b:
return gcd(a – b, b)
else:
return gcd(a, b – a)
Below is the implementation of the above approach.
C++
// C++ program to find GCD of two numbers#include <bits/stdc++.h>using namespace std;// Recursive function to return gcd of a and bint gcd(int a, int b){ // Everything divides 0 if (a == 0) return b; if (b == 0) return a; // Base case if (a == b) return a; // a is greater if (a > b) return gcd(a - b, b); return gcd(a, b - a);}// Driver codeint main(){ int a = 98, b = 56; cout << "GCD of " << a << " and " << b << " is " << gcd(a, b); return 0;} |
C
// C program to find GCD of two numbers#include <stdio.h>// Recursive function to return gcd of a and bint gcd(int a, int b){ // Everything divides 0 if (a == 0) return b; if (b == 0) return a; // Base case if (a == b) return a; // a is greater if (a > b) return gcd(a - b, b); return gcd(a, b - a);}// Driver codeint main(){ int a = 98, b = 56; printf("GCD of %d and %d is %d ", a, b, gcd(a, b)); return 0;} |
Java
// Java program to find GCD of two numbersimport java.io.*;class Test { // Recursive function to return gcd of a and b static int gcd(int a, int b) { // Everything divides 0 if (a == 0) return b; if (b == 0) return a; // Base case if (a == b) return a; // a is greater if (a > b) return gcd(a - b, b); return gcd(a, b - a); } // Driver code public static void main(String[] args) { int a = 98, b = 56; System.out.println("GCD of " + a + " and " + b + " is " + gcd(a, b)); }} |
Python3
# Python program to find GCD of two numbers# Recursive function to return gcd of a and bdef gcd(a, b): # Everything divides 0 if (a == 0): return b if (b == 0): return a # Base case if (a == b): return a # a is greater if (a > b): return gcd(a-b, b) return gcd(a, b-a)# Driver codeif __name__ == '__main__': a = 98 b = 56 if(gcd(a, b)): print('GCD of', a, 'and', b, 'is', gcd(a, b)) else: print('not found')# This code is contributed by Danish Raza |
C#
// C# program to find GCD of two numbersusing System;class GFG { // Recursive function to return gcd of a and b static int gcd(int a, int b) { // Everything divides 0 if (a == 0) return b; if (b == 0) return a; // Base case if (a == b) return a; // a is greater if (a > b) return gcd(a - b, b); return gcd(a, b - a); } // Driver code public static void Main() { int a = 98, b = 56; Console.WriteLine("GCD of " + a + " and " + b + " is " + gcd(a, b)); }}// This code is contributed by anuj_67. |
Javascript
// Javascript program to find GCD of two numbers// Recursive function to return gcd of a and bfunction gcd(a, b){ // Everything divides 0 if (a == 0) return b; if (b == 0) return a; // Base case if (a == b) return a; // a is greater if (a > b) return gcd(a-b, b); return gcd(a, b-a);}// Driver program to test above function let a = 98, b = 56; console.log("GCD of "+ a + " and " + b + " is " + gcd(a, b)); // This code is contributed by Mayank Tyagi |
PHP
<?php// PHP program to find GCD // of two numbers// Recursive function to return gcd of a and bfunction gcd($a, $b){ // Everything divides 0 if ($a == 0) return $b; if ($b == 0) return $a; // Base case if($a == $b) return $a ; // a is greater if($a > $b) return gcd( $a-$b , $b ) ; return gcd( $a , $b-$a ) ;}// Driver code$a = 98 ;$b = 56 ;echo "GCD of $a and $b is ", gcd($a , $b) ;// This code is contributed by Anivesh Tiwari?> |
GCD of 98 and 56 is 14
Time Complexity: O(min(a,b))
Auxiliary Space: O(1) No space is used as it is a tail recursion.
Program to Find GCD or HCF of Two Numbers
Given two numbers a and b, the task is to find the GCD of the two numbers.
Note: The GCD (Greatest Common Divisor) or HCF (Highest Common Factor) of two numbers is the largest number that divides both of them.
Examples:
Input: a = 20, b = 28
Output: 4
Explanation: The factors of 20 are 1, 2, 4, 5, 10 and 20. The factors of 28 are 1, 2, 4, 7, 14 and 28. Among these factors, 1, 2 and 4 are the common factors of both 20 and 28. The greatest among the common factors is 4.Input: a = 60, b = 36
Output: 12
Contact Us