Java Program to Find HCF of Two Numbers

Last Updated on May 18, 2023 by Prepbytes

The greatest number that evenly divides both two integers is known as the highest common factor (HCF). It is also known as the greatest common divisor (GCD) of the two numbers. Finding the HCF of two numbers is a common mathematical problem that arises in many areas of study, including algebra, number theory, and cryptography.

What is HCF (Highest Common Factor) or GCD (Greatest Common Divisor)?

HCF (Highest Common Factor) or GCD (Greatest Common Divisor) is the largest positive integer that divides two or more integers without leaving a remainder. It is an important concept in mathematics and has a wide range of applications in fields like number theory, cryptography, and computer science.

The HCF or GCD of 24 and 36, for instance, is 12.

Ways to Find the HCF of Two Numbers

We have different ways to find the HCF of two numbers:

Method 1: Naive Approach

The algorithm steps are as follows:

• Step 1: Initially set HCF to 1
• Step 2: Run a loop between [1, min(num1, num2)] throughout the iteration of (i).
• Step 3: List the largest number that divides both numbers 1 and 2 in your notes.
• Step 4: If i meets the conditions (num1% i == 0 && num2% i == 0), then i is the new HCF value.
• Step 5: HCF value printed

Code Implementation

class Main
{
  public static void main (String[]args)
  {
    int num1 = 24, num2 = 36, hcf=0;

    for (int i = 1; i <= num1 || i <= num2; i++)
      {
     if (num1 % i == 0 && num2 % i == 0)
        hcf = i;
      }

    System.out.println("The HCF: "+ hcf);
  }
}

Output

The HCF: 12

Method 2: Multiple Subtraction

The algorithm steps are as follows:

• Step 1: Run a while loop until num1 and num2 are not equal.
• Step 2: If num1 > num2, then num1 = num1 – num2.
• Step 3: If not, num2 equals num2 – num1.
• Step 4: Both num1 and num2 storage will be closed after the loop.

Code Implementation

class Main
{
  public static void main (String[]args)
  {
    int num1 = 24, num2 = 36, hcf=0;

    for (int i = 1; i <= num1 || i <= num2; i++)
      {
     if (num1 % i == 0 && num2 % i == 0)
        hcf = i;
      }

    System.out.println("The HCF: "+ hcf);
  }
}

Output

The HCF: 12

Method 3: Recursion-based Repeated Subtraction using the Modulo Operator

The algorithm steps are as follows:

• Step 1: Return an if b is equal to 0.
• Step 2: Otherwise, execute the function for value b, a%b, recursively, and return.

Code Implementation

class Main
{
  public static void main (String[]args)
  {
    int num1 = 24, num2 = 36, hcf=0;

    for (int i = 1; i <= num1 || i <= num2; i++)
      {
     if (num1 % i == 0 && num2 % i == 0)
        hcf = i;
      }

    System.out.println("The HCF: "+ hcf);
  }
}

Output

The HCF: 12

Method 4: Recursion-based Repeated Subtraction

The algorithm steps are as follows:

• Step 1: Upon determining that none of the input is 0, the total of the two values is returned.
• Step 2: Return either of the two numbers if the two inputs are equal.
• Step 3: Recursively call findHCF(num1 – num2, num2) if num1 is bigger than num2, otherwise Step 4: call findHCF(num1, num2-num1)

Code Implementation

class Main
{
  public static void main (String[]args)
  {
    int num1 = 24, num2 = 36, hcf;

      hcf = getHCF (num1, num2);
      System.out.println ("The HCF: " + hcf);
  }

  static int getHCF (int num1, int num2)
  {
    
    if (num1 == 0)
      return num2;

  
    if (num2 == 0)
      return num1;

   
    if (num1 == num2)
      return num1;

    
    if (num1 > num2)
      return getHCF (num1 - num2, num2);

    return getHCF (num1, num2 - num1);
  }
}

Output

The HCF: 12

Conclusion
Finding the HCF (Highest Common Factor) or GCD (Greatest Common Divisor) of two numbers is an important mathematical concept that has many practical applications. The greatest positive number that may be divided by two or more numbers without producing a residue is this one.

There are several methods to find the HCF/GCD of two numbers, including the prime factorization method, Euclid’s algorithm, and the division method and method you choose to find the HCF/GCD of two numbers will depend on the size of the numbers and the resources available to you.

Regardless of the method you use, finding the HCF/GCD of two numbers is an important mathematical skill that can be useful in many areas of study, including algebra, number theory, and cryptography.

Frequently Asked Questions

Q1. What is the difference between GCD and HCF?
Ans. GCD (Greatest Common Divisor) and HCF (Highest Common Factor) both refer to the same concept, which is the largest positive integer that divides two or more integers without leaving a remainder. The terms are used interchangeably in mathematics.

Q2. Why is finding the GCD/HCF important?
Ans. Finding the GCD/HCF of two or more numbers is an important mathematical concept with many practical applications. It is used in fields like cryptography, computer science, and number theory to solve complex problems.

Q3. Can the GCD/HCF be negative?
Ans. No, the GCD/HCF is always a positive integer by definition. The greatest positive number that may be divided by two or more numbers without producing a residue is this one.

Q4. What is the GCD/HCF of two prime numbers?
Ans. If two numbers are prime, then their GCD/HCF is 1. This is so because the only shared factor among prime integers is 1.

Q5. Can the GCD/HCF of two numbers be greater than the smaller number?
Ans. No, the GCD/HCF of two numbers cannot be greater than the smaller number. It is always a divisor of both numbers and therefore cannot be greater than the smaller number.

Q6. How is the GCD/HCF used in cryptography?
Ans. The GCD/HCF is used in cryptography to generate public and private keys for encryption and decryption. It is used to determine the modulus of the public key and to find the inverse of the private key.