C Program to Find HCF of two Numbers

There are many ways to find the H.C.F of two numbers is C programming. All codes below will take two integers from user and displays the H.C.F of those two integers.

1. Source Code to Find HCF or GCD


/* C Program to Find Highest Common Factor. */
#include <stdio.h>
int main()
{
    int num1, num2, i, hcf;
    printf("Enter two integers: ");
    scanf("%d %d", &num1, &num2);
    for(i=1; i<=num1 || i<=num2; ++i)
    {
        if(num1%i==0 && num2%i==0)   /* Checking whether i is a factor of both number */
            hcf=i;
    }
    printf("H.C.F of %d and %d is %d", num1, num2, hcf);
    return 0;
}

In this program, two integers are taken from user and stored in variable num1 and num2. Then i is initialized to 1 and for loop is executed until i becomes equal to smallest of two numbers. In each looping iteration, it is checked whether i is factor of both numbers or not. If i is factor of both numbers, it is stored to hcf. When for loop is completed, the H.C.F of those two numbers will be stored in variable hcf.

2. Source Code to Find HCF or GCD


#include <stdio.h>
int 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;
      }
  }
  return 0;
}

This program is little optimized than the program above to find H.C.F. In this program, smallest of two integers entered by user is stored in variable min. Then i is initialized to min and for loop is executed. In each looping iteration, whether i is factor of these two numbers is checked. If i is a factor of these two numbers then, i will be the highest common divisor and loop is terminated using break statement.

3. Source Code to Find HCF or GCD


#include<stdio.h>
int main()
{
    int num1,num2;
    printf("Enter two integers: ");
    scanf("%d %d",&num1,&num2);
    printf("HCF of %d and %d is ",num1 , num2);
    while(num1!=num2)
    {
        if(num1>num2)
            num1-=num2;
        else
            num2-=num1;
    }
    printf("%d",num1);
    return 0;
}

This is the best way to find HCF of two numbers. In this method, smaller number is subtracted from larger number and that number is stored in place of larger number. This process is continued until, two numbers become equal which will be HCF.

All source codes above displays the same output.

Output

Enter two integers: 14
35
HCF of 14 and 35 is 7