C program to find HCF of two numbers

A fundamental mathematical operation is finding the Highest Common Factor (HCF) or Greatest Common Divisor (GCD) of two numbers. The HCF of two numbers is the largest number that divides both of them without leaving a remainder. This article will guide you through writing a C program to find the HCF of two numbers using different methods.

Introduction

The HCF (or GCD) of two numbers is an essential concept in number theory and is used in various applications like simplifying fractions, cryptographic algorithms, and more. The two most common methods to find the HCF are the Euclidean algorithm and the consecutive integer checking algorithm.

Methods to Find HCF

Euclidean Algorithm

The Euclidean algorithm is an efficient method to compute the HCF of two integers. The algorithm is based on the principle that the HCF of two numbers also divides their difference. The steps are as follows:

1. Divide the larger number by the smaller number.
2. Replace the larger number with the smaller number and the smaller number with the remainder obtained from step 1.
3. Repeat the process until the remainder is 0.
4. The non-zero remainder at this stage is the HCF of the two numbers.

Consecutive Integer Checking Algorithm

This is a more straightforward but less efficient method compared to the Euclidean algorithm. The steps are as follows:

1. Identify the smaller of the two numbers.
2. Check if this smaller number divides both numbers without leaving a remainder.
3. If not, decrease the number by 1 and repeat the process until you find a number that divides both numbers.

C Program Using Euclidean Algorithm

Here is a C program that uses the Euclidean algorithm to find the HCF of two numbers:

#include <stdio.h>

int main() {
    int num1, num2;

    // Taking input from the user
    printf("Enter two integers: ");
    scanf("%d %d", &num1, &num2);

    // Euclidean algorithm to find HCF
    int a = num1;
    int b = num2;
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }

    // Displaying the result
    printf("HCF of %d and %d is %d", num1, num2, a);

    return 0;
}

Output

Enter two integers: 25 35
HCF of 25 and 35 is 5

C Program Using Consecutive Integer Checking Algorithm

Here is a C program that uses the consecutive integer checking algorithm to find the HCF of two numbers:

#include <stdio.h>

int main() {
    int num1, num2;

    // Taking input from the user
    printf("Enter two integers: ");
    scanf("%d %d", &num1, &num2);

    // Finding the smaller number
    int min = (num1 < num2) ? num1 : num2;

    // Consecutive integer checking algorithm to find HCF
    int hcf = 1;
    while (min > 0) {
        if (num1 % min == 0 && num2 % min == 0) {
            hcf = min;
            break;
        }
        min--;
    }

    // Displaying the result
    printf("HCF of %d and %d is %d", num1, num2, hcf);

    return 0;
}

Output

Enter two integers: 25 35
HCF of 25 and 35 is 5