GCD program in C

C language :

Dennis Ritchie developed the general-purpose computer language C at Bell Laboratories in 1972. Despite being an ancient language, it is extremely popular.

It is among the most widely used programming languages worldwide. Knowing C will make it easy for you to learn other popular programming languages like Java, Python, C++, C#, etc. because of how similar their syntax is.

Compared to other programming languages like Java and Python, C is very quick. It is possible to use C in both applications and technologies, making it incredibly adaptable.

GCD  ( Greatest Common Divisor ) :

The greatest common factor (GCF) that divides two or more numbers is known as the greatest common divisor (GCD). The highest common factor is another name for it (HCF). For instance, since both 15 and 10 can be divided by 5, 5 is the biggest common factor between both.

Mathematical Approach:

To find greatest common divisor using the mathematical approach we can find the greatest common divisor ( gcd ) using three different ways as shown below :

• Prime factorization method
• Euclid ‘ s division algorithm
• Long division method

The greatest common divisor of two numbers, a and b, is shown by the symbol gcd (a, b). We must list all the factors of the numbers and identify the biggest common factor in order to determine the gcd of the numbers.

Let's say there are three numbers: 4, 8, and 16. The factors 4, 8, and 16 are then:

                                  4 => 1,2,4

                                  8 ⇒ 1,2,4,8

                                 16 ⇒ 1,2,4,8,16

As a result, we can say that among the three numbers, 4 is the greatest common factor.

Real life applications of greatest common divisor (GCD ) :

In numerous instances in real life, as seen below, the idea of the greatest common factor or divisor is applied.

A store owner must pack 420 balls and 130 bats in a single day. She wants to pack them such that each set fits the same number of times in a box and takes up the smallest amount of space. What is the maximum number that can be included in each set for the purpose of packaging?

The needed integer in the above mentioned equation will be the greatest common divisor of 420 and 130.

Other applications include grouping people into smaller parts, placing students in rows and columns of an equal number, etc.

GCD (Greatest Common Divisor) program in C programming language :

We can find The GCD of the two given numbers in C language in three different ways as shown below:

• For loop and if else statement
• While loop and if else statement
• Using recursion

Now let us see how to find the greatest common divisor using for loop and if else condition using following code as shown below:

Example 1:

# include < stdio . h >
# include < conio . h >
void main ( void )
{
int a , b , i , ans;
printf ( “ Enter the value of integers “ );
scanf ( “ % d  % d “ , &a , &b );
for ( i = 1 , i <= a && i <= b , i++ )
{
if ( ( a % i == 0 ) && ( b % i == 0 ) ) 
{
ans = i;
} // if
} // for loop
printf ( “ GCD of % d and % d is : % d “ , a , b , ans );
} // main function

Input 1 and Output 1:

Enter the value of integers 
10
45
GCD of 10 and 45 is : 5

Now let us see how to find the greatest common divisor using while loop and if else condition using following code as shown below :

Example 2:

# include < stdio . h >
# include < conio . h >
void main ( void )
{
int a , b ;
printf ( “ Enter the value of integers “ );
scanf ( “ % d  % d “ , &a , &b );
while ( a != b )
{
if ( a> b)
{
a -= b ;
} // if block 
else
{
b -=a ;
} // else block
} // while loop
printf ( “ GCD of % d and % d is : % d “ , a , b , a);
} // main function

Output 2:

Enter the value of integers 
9
81
GCD of 10 and 45 is : 9

Now let us see how to find the greatest common divisor using the concept of recursion using following code as shown below :

Example 3:

# include < stdio . h >
# include < conio . h >
int gcd ( int a , int b );
void main ( void )
{
int a , b ;
printf ( “ Enter the value of integers “ );
scanf ( “ % d  % d “ , &a , &b );
printf ( “ GCD of % d and % d is : % d “ , a , b , gcd ( a , b ) );
} // main method
int gcd ( int a , int b )
{
if ( b != 0)
{
return gcd ( b , a % b );
} // if block
else
{
return a ;
} // else block
} // gcd method

Output 3 :

Enter the value of integers 
16
38
GCD of 10 and 45 is : 2