C program to find HCF (GCD) of two numbers

Write a C program enter two numbers and find the HCF (Highest Common Factor) using for loop. How to find GCD (Greatest Common Divisor) of any two given numbers using loops in C programming. Logic to find HCF of given number in C program.

Input first number: 12
Input second number: 30

HCF of 12 and 30: 6

Required knowledge

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

What is HCF (Highest Common Factor)?

HCF 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). For example -

Logic to find HCF of two numbers

Before I formally start explaining the logic. You must know how to check divisibility of any number.

• Program to check divisibility of any number.

Below is the step by step descriptive logic to find HCF.

1. Read two numbers from user. Store them in some variable say num1 and num2.
2. Initialize a variable to hold hcf i.e. hcf = 1.
3. Run a loop from 1 to minimum between both num1 and num2, increment the loop by 1 in each iteration. The loop structure should look like for(i=1; i<=min; i++). Assuming that min stores the minimum between num1 and num2.
4. Inside the loop check whether the current value of loop counter i.e. i clearly divides both numbers or not. If it divides then assign it to hcf i.e. hcf = i.

Program to find HCF of two numbers

/**
 * C program to find HCF (Highest Common Factor) of two numbers
 */

#include <stdio.h>

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

    /*
     * Read 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;
}

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

Happy coding ;)