C program to find HCF (GCD) of two numbers

Write a C program input two numbers from user and find the HCF using for loop. How to find GCD of two given numbers using loops in C programming. Logic to find HCF of two number in C programming.

Example

Input

Input first number: 12
Input second number: 30

Output

HCF of 12 and 30: 6

Required knowledge

Basic C programming, Conditional operator, If else, For loop

What is HCF?

HCF (Highest Common Factor) is the greatest number that divides exactly two or more numbers. HCF is also known as GCD (Greatest Common Divisor) or GCF (Greatest Common Factor).

HCF (Highest Common Factory)

Logic to find HCF of two numbers

Step by step descriptive logic to find HCF.

  1. Input two numbers from user. Store them in some variable say num1 and num2.
  2. Declare and initialize a variable to hold hcf i.e. hcf = 1.
  3. Find minimum between the given two numbers. Store the result in some variable say min = (num1<num2) ? num1 : num2;.
  4. Run a loop from 1 to min, increment loop by 1 in each iteration. The loop structure should look like for(i=1; i<=min; i++).
  5. Inside the loop check if i is a factor of two numbers i.e. if i exactly divides the given two numbers num1 and num2 then set i as HCF i.e. hcf = i.

Program to find HCF of two numbers

/**
 * C program to find HCF of two numbers
 */

#include <stdio.h>

int main()
{
    int i, num1, num2, min, hcf=1;

    /* Input two numbers from user */
    printf("Enter any two numbers to find HCF: ");
    scanf("%d%d", &num1, &num2);

    /* Find minimum between two numbers */
    min = (num1<num2) ? num1 : num2;

    for(i=1; i<=min; i++)
    {
        /* If i is factor of both number */
        if(num1%i==0 && num2%i==0)
        {
            hcf = i;
        }
    }

    printf("HCF of %d and %d = %d\n", num1, num2, hcf);

    return 0;
}

Move a step forward and learn the optimal approach to find HCF of two numbers.

Must learn – Program to find HCF using recursion.

Output

Enter any two numbers to find HCF: 12
30
HCF of 12 and 30 = 6

Happy coding 😉