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.

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 (Highest Common Factory)

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

Must know - Program to check divisibility of any number.

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

  1. Input 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;

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

Note: Do not confuse with the statement min = (num1<num2) ? num1 : num2;. It is used to find minimum between both numbers.

Read more - Program to find minimum between two numbers using conditional operator

Don't forget to learn this program using recursive approach.

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 😉

Write your doubts or suggestion. I will try my best to help. You must escape source code before commenting. To format your source code paste your source code inside
<pre><code> ----Your Source Code---- </code></pre>