C Programming Code Examples

C > For Loops and While Loops Code Examples

program to find HCF (GCD) of two numbers

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.

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).

Logic to find HCF of two numbers

    Input two numbers from user. Store them in some variable say j1 and j2.
    Declare and initialize a variable to hold hcf i.e. hcf = 1.
    Find minimum between the given two numbers. Store the result in some variable say min = (j1<j2) ? j1 : j2;.
    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++).
    Inside the loop check if i is a factor of two numbers i.e. if i exactly divides the given two numbers j1 and j2 then set i as HCF i.e. hcf = i.

#include <stdio.h>

int main()
{
    int i, j1, j2, min, hcf=1;

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

    /* Find minimum between two numbers */
    min = (j1<j2) ? j1 : j2;

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

    printf("HCF of %d and %d = %d\n", j1, j2, hcf);

    return 0;
}