C Program to find GCD Of Two Numbers

June 17, 2023

GCD of Two numbers in C

Here, in this section, we will discuss the GCD of two numbers in C. The Highest Common Multiple or the Greatest Common Divisor is the greatest number that exactly divides both numbers.

Example:-

The G.C.D of 14 and 40 is 8.

The G.C.D of 18 and 12 is 9
GCD

Various Methods to calculate the GCD

  • Using Prime Factorization,
  • Euclid’s Algorithm,
  • Lehmer’s GCD algorithm

Method 1

For a user input n1 & n2.

  • Use a for loop linearly traversing such that (i <= num1 || i <= num2)
  • Find max i value such that both n1 and n2 are divisible by i
    • (num1 % i == 0 && num2 % i == 0)

C Code (Method 1)

Run 
#include<stdio.h>

int main()
{
    int n1 = 18, n2 = 45, gcd = 1;
    
    for(int i = 1; i <= n1 || i <= n2; i++) {
        if(n1 % i == 0 && n2 % i == 0)
            gcd = i;
    }
    
    printf("The GCD of %d and %d is: %d", n1, n2, gcd);
    
    return 0;
}
// Time complexity : O(N)
// Space complexity : O(1)

Output

The GCD of 18 and 45 is: 9

Lowest Common Multiple (LCM)

 

Binary to Decimal to conversion

Octal to Decimal conversion

Hexadecimal to Decimal conversion

Method 2 

Euclidean Algorithm (also known as repeated Subtraction) is used for this method 

  • Euclidean Algorithm: GCD of two numbers remains constant even if we subtract the smaller number from the higher number.

Below is an example of a manual calculation that you can understand before moving ahead with the code.

C Code (Method 2)

Run 
#include<stdio.h>

// Using Euclidean Algorithm (Repeated Subtraction)
int main()
{
    int n1 = 104, n2 = 24, gcd = 1;
    
    while (n1 != n2)
    {
        if (n1 > n2)
            n1 -= n2;
        else
            n2 -= n1;
    }
    
    printf("The GCD: %d", n1, n2, gcd);
    
    return 0;
}

Output

The GCD: 8

Method 3

Euclidean Algorithm (also known as repeated Subtraction) is again used for this method 

This method has two changes –

  • Uses recursive approach
  • Also, handles if one of the numbers is 0

C Code (Method 3)

Run 
#include<stdio.h>

// Using Recursive Euclidean Algorithm (Repeated Subtraction)
int calcGCD(int n1, int n2)
{
    // Takes care of the case n1 is 0
    // We have given explanation above
    if (n1 == 0)
       return n2;
    
    // Takes care of the case n2 is 0
    // We have given explanation above
    if (n2 == 0)
       return n1;
  
    // base case
    if (n1 == n2)
        return n1;
  
    // n1 is greater
    if (n1 > n2)
        return calcGCD(n1 - n2, n2);

    // n2 is greater
    return calcGCD(n1, n2 - n1);
}

int main()
{
    int n1 = 45, n2 = 18;

    int gcd = calcGCD(n1, n2);
    
    printf("The GCD of %d and %d is: %d", n1, n2, gcd);
    
    return 0;
}

Output

The GCD of 45 and 18 is: 9

Method 4

Euclidean Algorithm (also known as repeated Subtraction) is again used for this method 

This method has two changes –

  • Reduced number of subtraction
  • Modulo operation helps us achieve these reduce subtraction

C Code (Method 4)

Run 
#include<stdio.h>

// Improved the time complexity in comparision to repeated subtraction
// Done by efficient usage of modulo operator in euclidean algorithm
int calcGCD(int a, int b)
{
    return b == 0 ? a : calcGCD(b, a % b);   
}

int main()
{
    int n1 = 45, n2 = 18;

    int gcd = calcGCD(n1, n2);
    
    printf("The GCD of %d and %d is: %d", n1, n2, gcd);
    
    return 0;
}

Output

The GCD of 45 and 18 is: 9

Prime Course Trailer

Related Banners

Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription

Get Prime
While loop in C

Lorem ipsum dolor sit amet, consectetur adipiscing elit. Ut elit tellus, luctus nec ullamcorper mattis, pulvinar dapibus leo.

Codes for Recursion

  • Power of a Number – C | C++ | Java | Python
  • Prime Number – C | C++ | Java | Python
  • Largest element in an array – C | C++ | Java | Python
  • Smallest element in an array – C | C++ | Java | Python
  • Reversing a Number – C | C++ | Java | Python
  • HCF of two numbers – C | C++ | Java | Python
  • LCM of two numbers – C | C++ | Java | Python
  • Program to calculate length of the string using recursion- C | C++ | Java | Python
  • Print All Permutations of a String- C | C++ | Java | Python
  • Given an integer N the task is to print the F(N)th term.- C | C++ | Java | Python
  • Given a list arr of N integers, print sums of all subsets in it- C | C++ | Java | Python
  • Last non-zero digit in factorial- C | C++ | Java | Python
  • Given a positive integer N, return the Nth row of pascal’s triangle – C | C++ | Java | Python
  • Given an integer N representing the number of pairs of parentheses, the task is to generate all combinations of well-formed(balanced) parentheses – C | C++ | Java | Python
  • Find the Factorial of a number using recursion – C | C++ | Java | Python
  • Find all possible Palindromic partitions of the given String – C | C++ | Java | Python
  • Find all the N bit binary numbers having more than or equal 1’s than 0’s – C | C++ | Java | Python
  • Given a set of positive integers, find all its subsets – C | C++ | Java | Python
  • Given a string s, remove all its adjacent duplicate characters recursively – C | C++ | Java | Python