Optimization by checking divisibility
The above method can be optimized based on the following idea:
If we notice the previous approach, we can see at some point, one number becomes a factor of the other so instead of repeatedly subtracting till both become equal, we can check if it is a factor of the other.
Illustration:
See the below illustration for a better understanding:
Consider a = 98 and b = 56
a = 98, b = 56:
- a > b so put a = a-b and b remains same. So a = 98-56 = 42 & b= 56.
a = 42, b = 56:
- Since b > a, we check if b%a=0. Since answer is no, we proceed further.
- Now b>a. So b = b-a and a remains same. So b = 56-42 = 14 & a= 42.
a = 42, b = 14:
- Since a>b, we check if a%b=0. Now the answer is yes.
- So we print smaller among a and b as H.C.F . i.e. 42 is 3 times of 14.
So HCF is 14.
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) { if (a % b == 0) return b; return gcd(a - b, b); } if (b % a == 0) return a; 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;} |
Java
public class GCD { // 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) { if (a % b == 0) return b; return gcd(a - b, b); } if (b % a == 0) return a; 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)); }}// This code is contributed by rambabuguphka |
Python3
def 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: if a % b == 0: return b return gcd(a - b, b) if b % a == 0: return a return gcd(a, b - a)# Driver codea = 98b = 56print(f"GCD of {a} and {b} is {gcd(a, b)}") |
C#
using System;public 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) { if (a % b == 0) return b; return GCD(a - b, b); } if (b % a == 0) return a; return GCD(a, b - a); } // Main method public static void Main(string[] args) { int a = 98, b = 56; Console.WriteLine("GCD of " + a + " and " + b + " is " + GCD(a, b)); }}// This code is add by Avinash Wani |
Javascript
// 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) { if (a % b === 0) { return b; } return gcd(a - b, b); } if (b % a === 0) { return a; } return gcd(a, b - a);}// Driver codelet a = 98;let b = 56;console.log(`GCD of ${a} and ${b} is ${gcd(a, b)}`); |
GCD of 98 and 56 is 14
Time Complexity: O(min(a, b))
Auxiliary Space: O(1)
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