Algorithm

The Euclidean algorithm is a simple and efficient method to get the Greatest Common Divisor (GCD) of two integer number.

The largest number that divides both of the input number without a remainder will be the output.

 

Step By Step algorithm of GCD:

  1. Take Two number - number1 and number2
  2. Continue a loop upto when number1 ≠ number2
    • If number1 > number2 
      • number1 = number1 - number2
    • else
      • number2 = number2 - number1
  3. GCD = number1

 

Here's an example of nth steps to get the GCD - 

Step k Equation Quotient and remainder
0 1071 = q0 462 + r0 q0 = 2 and r0 = 147
1 462 = q1 147 + r1 q1 = 3 and r1 = 21
2 147 = q2 21 + r2 q2 = 7 and r2 = 0; algorithm ends
 
 
 
 
 
 
 
 
 

Code Examples

#1 Code Example with C Programming

Code - C Programming

#include <stdio.h>

int main()
{
    int number1, number2;
    
    printf("Enter two numbers: ");
    scanf("%d %d", &number1, &number2);

    while(number1 != number2)
    {
        if(number1 > number2) {
            number1 = number1 - number2;
        } else {
            number2 = number2 - number1;
        }
    }
    
    printf("GCD = %d", number1);

    return 0;
}
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
15 45

Output

x
–
+
cmd
Enter two numbers: 15 45
GCD = 15

#2 GCD ProgramExample C Program using Recursion

Code - C Programming

#include <stdio.h>

int gcd(int number1, int number2){
   if(number2 == 0) {
      return number1;
   }
   
    return gcd(number2, number1 % number2);
}

int main()
{
    int number1, number2;
    
    printf("Enter two positive integers: ");
    scanf("%d %d", &number1, &number2);
    
    printf("GCD = %d", gcd(number1, number1));

    return 0;
}
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
15 45

Output

x
–
+
cmd
Enter two numbers: 15 45
GCD = 15
Advertisements

Demonstration

C Program Example to find GCD of Two numbers with Algorithm

Next
Appending into a File in C Programming