C program to find HCF (GCD) of two numbers

Previous Program Next Program

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.

Example

Input

Input first number: 12
Input second number: 30

Output

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 -

HCF of two numbers

Logic to find HCF of two numbers

Before I formally start explaining the logic. You must know how 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;
}

Note: Do not confuse with the statement min = (num1<num2) ? num1 : num2;. It is used to find minimum between both numbers. Read more about finding minimum using conditional operator.

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

Happy coding ;)

Recommended post

Previous Program Next Program

Labels: , , ,