The Greatest Common Divisor (GCD) is a mathematical concept that signifies the largest shared divisor of two or more numerical values. It denotes the greatest integer that can divide multiple numbers without any remainder. Hence, it is also referred to as the Highest Common Factor (HCF) of a pair of numbers. For instance, in the case of 20 and 28, their GCD is 4 as both numbers are wholly divisible by 1, 2, and 4 (with a remainder of 0), and the highest positive divisor common to 1, 2, and 4 is 4. Similarly, the GCD of 24 and 60 is 12.
GCD of two numbers using for loop
Let's examine a C program that calculates the Greatest Common Divisor (GCD) of two numbers by utilizing a for loop.
Gcd_for.c
#include <stdio.h>
#include <conio.h>
int main()
{
// declare the variables
int n1, n2, i, GCD_Num;
printf ( " Enter any two numbers: \n ");
scanf ( "%d %d", &n1, &n2);
// use for loop
for( i = 1; i <= n1 && i <= n2; ++i)
{
if (n1 % i ==0 && n2 % i == 0)
GCD_Num = i; /* if n1 and n2 is completely divisible by i, the divisible number will be the GCD_Num */
}
// print the GCD of two numbers
printf (" GCD of two numbers %d and %d is %d.", n1, n2, GCD_Num);
return 0;
}
Output
Enter any two numbers:
96
36
GCD of two numbers 96 and 36 is 12.
GCD of two numbers using while loop
Let's explore a C program that calculates the Greatest Common Divisor (GCD) of two numbers by utilizing a while loop.
Gcd_while.c
#include <stdio.h>
#include <conio.h>
int main()
{
// initialize the local variables num1 and num2
int num1 = 50, num2 = 60;
while (num1 != num2)
{
// if num1 is greater than num2, returns the num1.
if (num1 > num2)
{
num1 = num1 - num2;
}
// otherwise, it returns the num2.
else
{
num2 = num2 - num1;
}
}
// print the GCD of the number.
printf( " GCD of two numbers 50 and 60 is %d.", num2);
}
Output
GCD of two numbers 50 and 60 is 10.
Get the GCD of N numbers from the user
Let's explore a script that calculates the Greatest Common Divisor (GCD) of multiple numbers by gathering input from users.
gcdNum.c
#include <stdio.h>
#include <conio.h>
void main()
{
// declaration of the variables
int n1, n2 = -1;
printf (" Enter N numbers from the users ( 0 to exists from the loop) \n");
while ( 1)
{
scanf ( "%d", &n1); // A while loop continuously accepts the number
if ( n1 < 1) // n1 should be larger than 1
break;
else if ( n2 == -1)
n2 = n1; // assign the value of n1 to n2
else if(n1 < n2)
n2 = gcd_Num(n1, n2); // assign the function into the n2
else
n2 = gcd_Num( n2, n2); // else it stores the function value into the n2
}
printf (" \n GCD of all entered number is: %d", n2);
getch();
}
// Get the GCD of two numbers
int gcd_Num ( int x, int y)
{
int i;
for( i = x; i >= 1; i --)
{ // largest number that completely divides both number
if( x % i == 0 && y % i == 0)
break;
}
return i;
}
Output
GCD of two numbers 50 and 60 is 10.
Get the GCD of N numbers from the user
Let's explore a script that calculates the Greatest Common Divisor (GCD) of multiple numbers by gathering input from users.
gcdNum.c
#include <stdio.h>
#include <conio.h>
void main()
{
// declaration of the variables
int n1, n2 = -1;
printf (" Enter N numbers from the users ( 0 to exists from the loop) \n");
while ( 1)
{
scanf ( "%d", &n1); // A while loop continuously accepts the number
if ( n1 < 1) // n1 should be larger than 1
break;
else if ( n2 == -1)
n2 = n1; // assign the value of n1 to n2
else if(n1 < n2)
n2 = gcd_Num(n1, n2); // assign the function into the n2
else
n2 = gcd_Num( n2, n2); // else it stores the function value into the n2
}
printf (" \n GCD of all entered number is: %d", n2);
getch();
}
// Get the GCD of two numbers
int gcd_Num ( int x, int y)
{
int i;
for( i = x; i >= 1; i --)
{ // largest number that completely divides both number
if( x % i == 0 && y % i == 0)
break;
}
return i;
}
Output
Enter the N numbers from the users ( 0 to exists from the loop)
196
224
48
96
36
256
0
GCD of all entered number is: 4
Get the GCD of two numbers using user defined function
Let's explore a program that calculates the Greatest Common Divisor (GCD) of two numbers utilizing a user-defined function.
Func.c
#include <stdio.h>
#include <conio.h>
GetGCD (int x, int y);
int main()
{
int x, y, GCD = 0;
printf ( " Enter the first number \n ");
scanf ("%d", &x);
printf ( " Enter the second number \n ");
scanf ("%d", &y);
GCD = GetGCD( x, y); // call the GetGCD() function in main() function
// display the greatest common difference of two numbers
printf ( " GCD of the two numbers %d and %d is %d", x, y, GCD);
getch();
}
// function definition of the GetGCD
GetGCD ( int x, int y)
{
// A while loop will continue iterates till y is not equal to 0
while (y != 0)
{
if ( x > y) /* if x is greater than y, the if block is executed. */
{
x = x - y;
}
else
{
y = y - x;
}
}
return x;
}
Output
Enter the first number
96
Enter the second number
132
GCD of the two numbers 96 and 132 is 12
GCD of two numbers using the modulo operator
Let's explore a program that calculates the Greatest Common Divisor (GCD) of two numbers by utilizing the modulo operator.
Modulo.c
#include <stdio.h>
#include <conio.h>
void main()
{
// declaration of local variable
int x , y;
printf ( " Enter the first number: \n ");
scanf (" %d", &x);
printf ( " Enter the second number: \n ");
scanf (" %d", &y);
printf (" GCD of two number %d and %d is %d", x, y, GetGCD( x, y));
getch();
}
// use a recursive function to return GCD of two numbers x and y
int GetGCD (int x, int y)
{
if ( y == 0) // if y is equal to 0, it returns x
{
return x;
}
// use modulo operator to perform the divisibility
return GetGCD (y, x % y);
}
Output
Enter the first number:
256
Enter the second number:
92
GCD of two number 256 and 92 is 4
GCD of two numbers using Recursion
Let's explore a C program that utilizes recursion to calculate the Greatest Common Divisor (GCD) of two numbers.
Recursion.c
#include <stdio.h>
#include <conio.h>
int GCD_Rec(int num1, int num2);
int main()
{
int num1, num2;
printf( " Enter any two positive numbers \n");
scanf("%d %d", &num1, &num2);
// call and print the GCD of two number using GCD_Rec()
printf(" GCD of two numbers %d and %d is %d", num1, num2, GCD_Rec(num1, num2));
return 0;
}
int GCD_Rec(int num1, int num2)
{
if (num2 != 0)
{
return GCD_Rec( num2, num1 % num2);
}
else
{
return num1;
}
}
Output
Enter any two positive numbers:
60
48
GCD of two numbers 60 and 48 is 12
In the provided code snippet, the recursive function GCD_Rec iterates by invoking itself repeatedly until the num2 variable reaches a value of 0.
GCD of three numbers using if_else and for loop
Let's explore a C program that calculates the Greatest Common Divisor (GCD) of three numbers by utilizing if-else statements and a for loop.
Gcd_num.c
#include <stdio.h>
#include <conio.h>
void main()
{
// declare the variable x, y and z.
int n1, n2, n3;
printf (" Enter any positive numbers: \n ");
scanf ( " %d %d %d", &n1, &n2, &n3);
int GCD;
// use for loop to define the function and condition
for ( GCD = GCD_fun( n1, n2, n3); GCD >= 1; GCD--)
{
if (n1 % GCD == 0 && n2 % GCD == 0 && n3 % GCD == 0)
{
break;
}
}
printf (" GCD of three numbers %d, %d and %d is %d", n1, n2, n3, GCD);
getch();
}
int GCD_fun ( int x, int y, int z)
{
if ( x >= y && x >= z)
{
return x;
}
else if ( y >= x && y >= z)
{
return y;
}
else if ( z >= x && z >= y)
{
return z;
}
}
Output
Enter any positive numbers:
98
49
56
GCD of three numbers 98, 49 and 56 is 7