Skip to main content

ProwessApps

Learn · Practice · Excel
About Contact
Login / Register

Java Program to calculate hcf and lcm of two numbers.

Java Code Example — Simple Programs

ADVERTISEMENT

Java Program to calculate hcf and lcm of two numbers.

Objective

Write a Java program to calculate the Highest Common Factor (HCF) and Least Common Multiple (LCM) of two numbers.

Algorithm / Approach

  1. Read two numbers x and y.
  2. Identify the greater number (gr) and lower number (low).
  3. Run a while loop as long as low != 0.
  4. Calculate the remainder temp = gr % low.
  5. Shift values: gr = low and low = temp.
  6. When the loop ends, gr holds the HCF.
  7. Calculate LCM using the formula: LCM = (x * y) / HCF.
Test.java 
import java.util.Scanner;
class Test {
 public static void main(String[] a)
 {
  Scanner s=new Scanner(System.in);
  System.out.print("Enter Num1: ");
  int x = s.nextInt();
  System.out.print("Enter Num2: ");
  int y = s.nextInt();
  int gr =(x >= y)?x:y;
  int low =(x < y)?x:y;
  int temp, lcm;
  while(low!=0) {
   temp = gr % low;
   gr = low;
   low = temp;
  }
  System.out.println("HCF = "+gr);
  lcm = (x*y)/gr;
  System.out.print("LCM = "+lcm); 
 }
}

Expected Output

Enter Num1: 12
Enter Num2: 15
HCF = 3
LCM = 60

Explanation of the Program

  • The program implements the Euclidean algorithm to find the HCF (or GCD - Greatest Common Divisor).
  • It continuously replaces the larger number with the smaller number and the smaller number with the remainder until the remainder reaches 0.
  • The LCM is mathematically related to the HCF. The product of two numbers is equal to the product of their HCF and LCM.

Complexity

Time Complexity O(log(min(x, y))) - The Euclidean algorithm is highly efficient.
Space Complexity O(1)

Common Mistakes

  • Using the modified gr and low values to calculate the LCM instead of the original x and y inputs.
  • Trying to find HCF by brute force checking all divisors from 1 to minimum(x, y), which is slow.
ADVERTISEMENT