How to Find HCF of Two Numbers in C?

You can find the Highest Common Factor (HCF), also known as the Greatest Common Divisor (GCD), of two numbers in C using several methods. Here's a common and efficient approach:

Method: Iterative Approach

This method involves iterating from 1 up to the minimum of the two numbers and checking for divisibility.

Steps:

1. Initialize hcf to 1: Start with a variable hcf initialized to 1. This variable will store the HCF as we find larger common factors.

2. Find the Minimum: Determine the smaller of the two numbers, n1 and n2. This is because the HCF cannot be greater than the smaller number.

3. Iterate and Check Divisibility: Loop from i = 1 to the minimum value found in step 2. For each i, check if both n1 and n2 are perfectly divisible by i (i.e., the remainder is 0 when n1 and n2 are divided by i).

4. Update hcf: If i divides both n1 and n2, update the hcf to i.

5. Return hcf: After the loop finishes, the variable hcf will hold the Highest Common Factor of the two numbers. Return this value.

C Code Example:

#include <stdio.h>

int findHCF(int n1, int n2) {
  int hcf = 1;
  int min = (n1 < n2) ? n1 : n2; // Find the minimum

  for (int i = 1; i <= min; i++) {
    if (n1 % i == 0 && n2 % i == 0) {
      hcf = i;
    }
  }
  return hcf;
}

int main() {
  int num1, num2;

  printf("Enter two integers: ");
  scanf("%d %d", &num1, &num2);

  int hcf = findHCF(num1, num2);
  printf("HCF of %d and %d is %d\n", num1, num2, hcf);

  return 0;
}

Explanation of the Code:

• #include <stdio.h>: Includes the standard input/output library for functions like printf and scanf.
• findHCF(int n1, int n2): This function takes two integers as input and returns their HCF.
• int hcf = 1;: Initializes the hcf variable to 1.
• int min = (n1 < n2) ? n1 : n2;: Uses the ternary operator to find the minimum of n1 and n2.
• for (int i = 1; i <= min; i++): The for loop iterates from 1 up to the minimum value.
• if (n1 % i == 0 && n2 % i == 0): Checks if both n1 and n2 are divisible by i. The % operator gives the remainder of a division.
• hcf = i;: If i is a common factor, update hcf.
• return hcf;: Returns the calculated HCF.
• main() function: Prompts the user to enter two numbers, calls the findHCF function, and prints the result.

Example Usage:

If you enter 12 and 18, the output will be:

HCF of 12 and 18 is 6

Alternative Method: Euclidean Algorithm

The Euclidean algorithm is a more efficient method, especially for larger numbers.

Euclidean Algorithm Code Example:

#include <stdio.h>

int findHCF_Euclidean(int a, int b) {
  if (b == 0) {
    return a;
  }
  return findHCF_Euclidean(b, a % b);
}

int main() {
    int num1, num2;

    printf("Enter two integers: ");
    scanf("%d %d", &num1, &num2);

    int hcf = findHCF_Euclidean(num1, num2);
    printf("HCF of %d and %d is %d\n", num1, num2, hcf);

    return 0;
}

This method recursively finds the HCF based on the principle that the HCF of two numbers doesn't change if the larger number is replaced by its difference with the smaller number. This is optimized further by using the modulo operator (%) to get the remainder, reducing the number of steps needed.