Friday, December 11, 2015

GCD program

C Program to Find GCD of two Numbers

Note: GCD of any two numbers (say a and b) lies between 1 and minimum of two numbers


LCM(a,b) * GCD(a,b)=a*b

main()
{
          int num1, num2, min,i;
          printf("Enter two integers: ");
          scanf("%d %d", &num1, &num2);
 
min=(num1>num2)?num2:num1; /* minimum value is stored in variable min */
          for(i=min;i>=1;--i)
          {
                   if(num1%i==0 && num2%i==0)
                   {
                                      printf("HCF of %d and %d is %d", num1, num2,i);
                             break;
                   }
          }
}






C Program to Find GCD of n Numbers

Note: GCD of any n numbers (say a and b) lies between 1 and minimum of n numbers




main()
{
          int a[100], n, min,i;
          printf("Enter number of elements in an array");
          scanf("%d",&n);
          printf("Enter %d integers: ",n);
          for(i=0;i<n;i++)
                      scanf("%d", &a[i]);

/* Find minimum value and store it in variable min */

min=a[0];

for(i=1;i<n;i++)
{
      if(a[i]<min)
          min=a[i];
}

          for(i=min;i>=1;--i)
          {
                    count=0;
                   for(j=0;j<n;j++)
                   {
                            if(a[j]%i==0)
                                  count++;
                    }
                   if(count==n)
                   {
                                      printf("HCF is %d", i);
                                      break;
                   }
          }
}