C program to find GCD of two numbers

C program to find GCD of two numbers

Question

Write a C program to find GCD of two numbers. Get the input from the user.

 

We have to find the greatest common divisor of two numbers. To find that first we have to know all the divisors of the number. Divisors of 30 and 24 is mentioned in the diagram. In that 6 is the greatest divisor which is common in both the list. Let’s see the logic.

Logic

  • Since we have to find the greatest divisor. We start our search from the ending of the smaller number. In the example 24 is the smaller number.
  • Starting from 24 check whether the number divides both the number(24 and 30)
  • If it doesn’t divide then decrement the count.
  • Repeat this until you find the greatest common divisor.

Program

#include<stdio.h>
int main()
{
    int a, b,i;
    printf("enter two numbers");
    scanf("%d%d",&a,&b);
    /*find the smallest number of both*/
    if(a>b)
        i=b;        //b is smaller
    else
        i=a;        //a is smaller

    /*we search from ending to find the number which divides both a and b
     *EX: if given numbers a=30 and b=15 =>> i=15
     */
    for(;i>0;i--)
    {
        if(a%i==0&&b%i==0 )     //i divides both a and b
        {
            printf("%d",i);
            break;              //break loop after finding gcd
        }

    }

}
</pre>

 

 

 

 

Follow For Instant Updates

Join WhatsApp Group: link
Join our Telegram Channel: link
Like our Facebook Page:  link
Subscribe to our Youtube channel: link

Sree Hari Sanjeev

The founder of Wisdom Overflow. Software Developer at Zoho Corporation.
0 0 votes
Article Rating
Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments
0
Would love your thoughts, please comment.x
()
x