Iterative implementation for GCD of two numbers using Euclidean Algorithm
Below is the iterative way to find the GCD of two numbers using Euclidean algorithm.
C++
// C++ program to find GCD of two numbers#include <bits/stdc++.h>using namespace std;// Iterative function to return gcd of a and bint gcd(int a, int b){ while (a > 0 && b > 0) { if (a > b) { a = a % b; } else { b = b % a; } } if (a == 0) { return b; } return 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>// Iterative function to return gcd of a and bint gcd(int a, int b){ while (a > 0 && b > 0) { if (a > b) { a = a % b; } else { b = b % a; } } if (a == 0) { return b; } return 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 { // Iterative function to return gcd of a and b static int gcd(int a, int b) { while (a > 0 && b > 0) { if (a > b) { a = a % b; } else { b = b % a; } } if (a == 0) { return b; } return 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
# Itervative function to return gcd of a and bdef gcd(a, b): # Everything divides 0 while(a > 0 and b > 0): if (a > b): a = a % b else: b = b % a if (a == 0): return b return 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') |
C#
// C# program to find GCD of two numbersusing System;class GFG { // Iterative function to return gcd of a and b static int gcd(int a, int b) { while (a > 0 && b > 0) { if (a > b) { a = a % b; } else { b = b % a; } } if (a == 0) { return b; } return 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 number// Recursive function to return gcd of a and bfunction gcd(a, b){ // Everything divides 0 while (a > 0 && b > 0) { if (a > b) { a = a % b; } else { b = b % a; } } if (a == 0) { return b; } return a;}// Driver codelet a = 98;let b = 56;console.log(`GCD of ${a} and ${b} is ${gcd(a, b)}`);// This code is contributed by _saurabh_jaiswal |
Output
GCD of 98 and 56 is 14
Time Complexity: O(log(min(a,b)))
Auxiliary Space: O(1)
GCD of two numbers using inbuilt function:
Languages like C++ have inbuilt functions to calculate GCD of two numbers.
Below is the implementation using inbuilt functions.
C++
// c++ program to find gcd using inbuilt functions#include <algorithm>#include <iostream>using namespace std;int main(){ int a = 98, b = 56; cout << "The gcd of a and b is " << __gcd(a, b) << endl; return 0;} |
Java
// JAVA program to find gcd using inbuilt functionsimport java.math.BigInteger;import java.util.*;public class GFG { public static void main(String[] args) { int a = 98, b = 56; int gcd = gcd(a, b); System.out.println("The gcd of a and b is " + gcd); } public static int gcd(int a, int b) { BigInteger bigA = BigInteger.valueOf(Math.abs(a)); BigInteger bigB = BigInteger.valueOf(Math.abs(b)); BigInteger gcd = bigA.gcd(bigB); return gcd.intValue(); }}// This code is contributed by Taranpreet Singh. |
Python3
# Python program to find gcd using inbuilt function using math libraryimport math#Driver codeif __name__ == '__main__': a = 98 b = 56 gcd_result = math.gcd(a, b) # inbuilt function gcd() using math library print("The gcd of a and b is", gcd_result)# This code is contributed by guptapratik |
C#
using System;class Program{ static void Main() { int a = 98, b = 56; Console.WriteLine($"The gcd of a and b is {GCD(a, b)}"); } static int GCD(int a, int b) { return Math.Abs(b == 0 ? a : GCD(b, a % b)); }} |
Javascript
function gcd(a, b) { if (b === 0) { return a; } else { return gcd(b, a % b); }}// Example usageconst a = 98;const b = 56;console.log("The gcd of a and b is " + gcd(a, b));// Contributed By Siddhesh22 |
Output
The gcd of a and b is 14
Time Complexity: O(log(min(a, b)))
Auxiliary Space: O(1)
Please refer GCD of more than two (or array) numbers to find HCF of more than two numbers.
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