Find g.c.d of two number using c program


Definition of HCF (Highest common factor):

HFC is also called greatest common divisor (gcd). HCF of two numbers is a largest positive numbers which can divide both numbers without any remainder.  For example HCF of two numbers 4 and 8 is 2 since 2 is the largest positive number which can dived 4 as well as 8 without a remainder. 

Logic of HCF or GCD of any two numbers:

In HCF we try to find any largest number which can divide both the number.
For example: HCF or GCD of 20 and 30
Both number 20 and 30 are divisible by 1, 2,5,10.
HCF=max (1, 2, 3, 4, 10) =10

Logic for writing program:

It is clear that any number is not divisible by greater than number itself. In case of more than one numbers, a possible maximum number which can divide all of the numbers must be minimum of all of that numbers.

For example: 10, 20, and 30
Min (10, 20, 30) =10 can divide all there numbers. So we will take one for loop which will start form min of the numbers and will stop the loop when it became one, since all numbers are divisible by one. Inside for loop we will write one if conditions which will check divisibility of both the numbers.
Program:


Write a c program for finding gcd (greatest common divisor) of two given numbers


#include<stdio.h>

int main(){

    int x,y,m,i;

    printf("Insert any two number: ");

    scanf("%d%d",&x,&y);
    if(x>y)
         m=y;
    else
         m=x;

    for(i=m;i>=1;i--){
         if(x%i==0&&y%i==0){
             printf("\nHCF of two number is : %d",i) ;
             break;
         }
    }
    return 0;
}


Other logic : HCF (Highest common factor)  program with two numbers in c 



#include<stdio.h>
int main(){
int n1,n2;
printf("\nEnter two numbers:");
scanf("%d %d",&n1,&n2);
while(n1!=n2){
if(n1>=n2-1)
n1=n1-n2;
else
n2=n2-n1;
}
printf("\nGCD=%d",n1);
return 0;
}


HCF  program with multiple numbers in c 


#include<stdio.h>
int main(){
    int x,y=-1;
    printf("Insert numbers. To exit insert zero: ");
   
    while(1){
         scanf("%d",&x);
         if(x<1)
             break;
         else if(y==-1)
             y=x;
         else if (x<y)
             y=gcd(x,y);
         else
             y=gcd(y,x);
    }

    printf("GCD is %d",y);
   
    return 0;
}

int gcd(int x,int y){
    int i;
    for(i=x;i>=1;i--){
         if(x%i==0&&y%i==0){
             break;
         }
    }
    return i;
}


51 comments:

  1. im finding solution for this programme since 5days.now i got the logic but better to explain the programme in theriotically please.its reaaly need for basic learner like me.

    regard
    geeta

    ReplyDelete
  2. Excellent logic i got it

    ReplyDelete
  3. Excellent Good Try

    and i want gcd for more than two numbers if any one knows please explain

    ReplyDelete
    Replies
    1. try on your own

      Delete
    2. /*To find GCD of two given numbers*/

      /*File inclusion*/
      #include
      #include

      main()
      {
      int a,b,c,d,f=0;
      clrscr();
      printf("To find GCD, please enter the two numbers..\n");
      scanf("%d %d",&a,&b);
      if(a<b)
      {
      c=a; /*This if-else condition will take least value among the two values a and b*/
      }
      else
      {
      c=b;
      }
      printf("%d and %d are divisible by:\n",a,b);
      for(d=1;d<=c;d++)
      {

      if(a%d==0 && b%d==0)
      {
      printf("%d ",d);
      if(f<d)
      {
      f=d;
      }
      }
      }
      printf("\n\nThe GCD is...%d",f);
      getch();
      return;
      }

      -Answer from INDIA

      Delete
    3. /*To find GCD of two given numbers*/

      /*File inclusion*/
      #include
      #include

      main()
      {
      int a,b,c,d,e,f=0;
      clrscr();
      printf("To find GCD, please enter the two numbers..\n");
      scanf("%d %d %d",&a,&b,&e);
      if(a<b)
      {
      if(a<e)
      {
      c=a; /*This if-else condition will take least value among the three values a , b and e*/
      }
      else
      {
      c=e;
      }
      }
      else
      {
      if(b<e)
      {
      c=b;
      }
      else
      {
      c=e;
      }
      }
      printf("%d , %d and %d are divisible by:\n",a,b,e);
      for(d=1;d<=c;d++)
      {

      if(a%d==0 && b%d==0 && e%d==0)
      {
      printf("%d ",d);
      if(f<d)
      {
      f=d;
      }
      }
      }
      printf("\n\nThe GCD is...%d",f);
      getch();
      return;
      }

      -Answer from INDIA

      Delete
    4. above is for finding gcd of 3 numbers

      Delete
  4. gcd of 3 numbers with high efficiency

    #include
    int gcd(int , int , int);
    int main()
    {
    int i , j , k , g;
    scanf("%d %d %d", &i , &j , &k);

    g = gcd(i , j , k);
    printf("%d",g);

    return 0;
    }

    int gcd(int i , int j , int k)
    {
    int least;
    least = i;
    while(!( (i == j) && (j == k) ) )
    {
    i = (i == 0 ? least : i);
    j = (j == 0 ? least : j);
    k = (k == 0 ? least : k);
    if(i <= j)
    {
    if(i <= k)
    least = i;
    else
    least = k;
    }
    else
    {
    if(j <= k)
    least = j;
    else
    least = k;
    }
    i = i % least;
    j = j % least;
    k = k % least;
    }
    return least;

    }

    ReplyDelete
    Replies
    1. rare...........!!!!!!!!!

      Delete
    2. really encouraging but some of the c programs posted here need to be edited for them to give the right answer rhyming with what we know!!!!! other wise guys you are doing marvelous

      Delete
  5. In "Other logic : HCF program with two numbers in c"- In the first if statement condition n1>=n2-1,
    here "-1" is redundant. I think.

    ReplyDelete
  6. iam not able to understand the real logic behind this .pls send stepby step solution to find the hcf of two numbers ......

    ReplyDelete
  7. gcd of two numbers using recurssive function?
    if ne one knws plz post

    ReplyDelete
  8. while(y!=0)
    temp=x%y;
    x=y;
    y=temp;

    gcd logic correct r not

    ReplyDelete
  9. printf("THANQ VERY MUCH");

    (-.-)

    ReplyDelete
  10. The Logic is simple...i used array ...it is not necessary...just to explain how it works...the output shows the step by step procedure to find hcf



    #include

    void main()
    {
    int x,y,f1[100],f2[100],c[1000],i,j,k,l,m,n;
    printf("\ninput the 2 numbers whose hcf is to be found\n");
    scanf("%d%d",&x,&y);
    for(j=0,i=1;i<=x/2;i++)
    {
    if(x%i==0)
    {
    f1[j]=i;
    j++;
    }
    }
    f1[j]=x;
    j++;
    for(k=0,i=1;i<=y/2;i++)
    {
    if(y%i==0)
    {
    f2[k]=i;
    k++;
    }
    }
    f2[k]=y;
    k++;

    printf("\nfactors of first number\n");
    for(i=0;i<j;i++)
    { printf("%d ",f1[i]);
    }
    printf("\nfactors of second number\n");
    for(i=0;i<k;i++)
    { printf("%d ",f2[i]);
    }

    for(m=0,i=0;i<j;i++)
    {
    for(n=0;n<k;n++)
    {
    if(f1[i]==f2[n])
    {
    c[m]=f1[i];
    m++;
    }
    }
    }
    printf("\nCommon factors\n");
    for(i=0;i<m;i++)
    printf("%d ",c[i]);
    printf("\nGCD (Greatest Common Factor): %d \n",c[i-1]);
    printf("\nLCM (Least Common Factor: ");
    if(c[1]=='\0')
    printf("%d",c[0]);
    else
    printf("%d",c[1]);

    getch();

    }

    ReplyDelete
  11. #include

    #include

    int GCD(int x, int y);

    int main()

    {
    int x;

    int y;

    int z;

    printf("Enter the two digits you wich to look for their common difference \n");
    scanf("%d%d \n", &x , &y );
    printf("The Greatest common divisor: %d\n", GCD(x , y));
    return 0;
    }
    /* the definition of the function greatest common divisor*/
    int GCD(int x, int y)

    {

    int z;


    if( (int) (x*y)/2 == z);

    return (x*y)/2;

    }

    ReplyDelete
    Replies
    1. pleaz the directives are stdio.h and stdlib.h i will be glad with any reasonable criticism

      Delete
  12. can any one plz write a c program to find minimal or conical cover of functional dependency >>>?

    ReplyDelete
  13. Thanks.
    Really helpful for me .

    ReplyDelete
  14. I got a much easier logic than this..

    Suppose a=16, b=12:
    then while (r!=0)
    a%b=r;
    a=b;
    b=r;
    What say? ;)

    ReplyDelete
  15. @komal
    Bhai apna logic samjhao toh yaar...
    Incomprehensible...

    ReplyDelete
  16. Very nice and simple and super by cquestions

    ReplyDelete
  17. print the next two number and use only one variable for each question
    a)0,5,10,15,20,25,?,?
    b)0,2,4,6,8,10,?,?
    c)1,2,4,8,16,32,?,?

    who can help me..please.....

    ReplyDelete
  18. #include
    #include
    voidmain()
    {
    int a,b,n,m,gcd;
    clrscr();
    printf("enter the valuse of a,b");
    scanf("%d%d",&a,&b);
    n=a;
    m=b;
    while(n!=m)
    {
    if(n>m)
    n=n-m
    else
    m=m-n
    }
    gcd=n;
    printf("gcd of %d and %d is %d",a,b,gcd);
    getch();
    }

    ReplyDelete
  19. #include
    #include
    void main()
    {
    int a,b,c;
    printf("Enter 2 digit:");
    scanf("%d%d",&a,&b);
    while(a%b!=0)
    {
    c=a%b;
    a=b;
    b=c;
    }
    printf("GCD is %d",b);
    }

    ReplyDelete
  20. Sir plzz solve this problem...
    Euclid's Algorithm is a well-known algorithm for computing the greatest common divisor (GCD) of two numbers.
    The algorithm is based on the observation that, if r is the remainder when a is divided by b, then the common divisors of a and b are the same as the common divisors of b and r. Thus we can use the equation

    GCD (a, b) = GCD (b, r)

    to successively reduce the problem of computing a GCD to the problem of computing the GCD of smaller and smaller pairs of integers. For example,

    GCD (36, 20) = GCD (20, 16) = GCD (16, 4) = GCD (4, 0) = 4

    Implies that the GCD of 36 and 20 is 4. It can be shown that for any two starting numbers, this repeated reduction eventually produces a pair where the second number is 0. Then the GCD is the other number in the pair.

    Write a method named gcd that computes the greatest common divisor of two integers. Add some code to main that tests the new method.

    ReplyDelete
  21. Use Euclidean Algorithm of NUMBER THEORY , best solution .....

    #include
    main()
    {
    int a,b,gcd,temp,a1,b1; /* we need to make a>b */

    printf("Enter two numbers a and b \n");
    scanf("%d%d",&a,&b);
    a1=a; b1=b;
    if(a<b)
    { temp=a;
    a=b;
    b=temp; }

    while((a%b)!=0)
    {
    temp=a%b;
    a=b;
    b=temp;

    }

    gcd=temp;

    printf("The GCD of %d and %d is %d\n",a1,b1,gcd);

    }

    ReplyDelete
    Replies
    1. This is how Euclidean Algorithm Work.

      In this we take two numbers a and b (a>b) and we need to find the gcd of them.
      So first we apply division algorithm a=q1*b+r1 if r1=0 then b/a and gcd(a,b)=b else we divide b by r1 i.e. b=q2*r1 + r2; and if r2=0 gcd=r1 else r1=q3*r2+r3
      and continue in similar fashion we get
      r_n-2=q_n*r_n-1+r_n;
      r_n-1=q_n+1*r_n +0;
      so gcd(a,b)=r_n using if a=bq+r;
      gcd(a,b)=gcd(b,r);

      Delete
  22. Euclid's algorithm based program to find gcd of two number.

    #include
    main()
    {
    int a, b, temp;
    scanf("%d %d", &a, &b);
    while(b)
    {
    temp = b;
    b = a%b;
    a = temp;
    }
    printf("%d", a);
    }

    ReplyDelete
  23. #include
    #include
    int main()
    {
    int m,n,gcd,r;
    printf("enter the first number");
    scanf("%d",&m);
    printf("enter the second number");
    scanf("%d",&n);
    while(m%n!=0)
    {
    r=m%n;
    m=n;
    n=r;
    }
    gcd=n;
    printf("greatest common divisor of m and n is %d",gcd);
    return 0;
    getch();
    }

    ReplyDelete
  24. @admin - The statement in the starting saying

    "For example HCF of two numbers 4 and 8 is 2 since 2 is the largest positive number which can dived 4 as well as 8 without a remainder. "

    is wrong. HCF of 4 and 8 is 4.

    ReplyDelete
  25. hcf of 4 and 8 is 4 and not 2

    ReplyDelete
  26. Khyati Thakkar11/13/13, 2:40 AM

    Int GCD(int m,int n)
    {
    If (m<n)
    return (GCD(n,m));
    If (m%n==0)
    return (n);
    return(GCD(n,m%n));
    }

    ReplyDelete
  27. write a program to withdraw money in atm

    ReplyDelete
  28. Recursion one is good

    ReplyDelete
  29. if(x>y)
    m=y;
    else
    m=x;
    isnt required because the gcd of two number is always equal to or lesser than least number of given two numbers.
    for example:
    111 and 666 are given as two inputs then the gcd will either equal to 111 or less than it,here gcd is 111.so assign m as any one of the two inputs "i" in the for loop will definitely come to 111 and may go below it in other examples.

    ReplyDelete
  30. Greatest Common Divisor (GCD) of two integers a and b, denoted by gcd(a,b), is the greatest integer dividing both a and b. For example gcd(8,4) = 4, gcd(5,7) = 1, gcd(9,3)=3 etc. Write down a program that will take two integers as input and will calculate the GCD of two using loop. Draw a table showing values of each variables in every step of the loop for gcd(32,12).

    ReplyDelete
  31. Your "other HCF logic" has bug it wont work properly for (5,3)

    ReplyDelete
  32. #include
    main()
    {
    int n1,n2,n3;
    scanf("%d %d",&n1 &n2);
    n3=gcd(n1,n2);
    printf("GCD of %d & %d =%d\n",n1,n2,n3);
    }
    int gcd(int i,int j);
    {
    int temp;
    if(i<j)
    {
    temp=i;
    i=j;
    j=temp;
    }
    while(i%j!=0)
    {
    temp=i%j;
    i=j;
    j=temp;
    }
    return(j);
    }

    ReplyDelete
  33. int gcd(int a, int b)
    {
    if (b==0)
    return a;
    else
    return gcd(b,a%b);
    }

    ReplyDelete
  34. /* Write a C program to find the GCD and LCM of two integers *
    * output the results along with the given integers. Use Euclids' algorithm*/
    #include
    #include

    void main()
    {
    int num1, num2, gcd, lcm, remainder, numerator, denominator;
    clrscr();

    printf("Enter two numbers\n");
    scanf("%d %d", &num1,&num2);

    if (num1 > num2)
    {
    numerator = num1;
    denominator = num2;
    }
    else
    {
    numerator = num2;
    denominator = num1;
    }
    remainder = num1 % num2;
    while(remainder !=0)
    {
    numerator = denominator;
    denominator = remainder;
    remainder = numerator % denominator;
    }
    gcd = denominator;
    lcm = num1 * num2 / gcd;
    printf("GCD of %d and %d = %d \n", num1,num2,gcd);
    printf("LCM of %d and %d = %d \n", num1,num2,lcm);
    } /* End of main() */
    /*------------------------
    Output
    RUN 1
    Enter two numbers
    5
    15
    GCD of 5 and 15 = 5
    LCM of 5 and 15 = 15
    ------------------------------*/

    ReplyDelete