LCM Program in Java

Last Updated on April 26, 2023 by Prepbytes

LCM is an acronym for Least Common Multiple. LCM is an important mathematical concept that is widely used in solving real-world problems. It is defined as the smallest positive integer that is divisible by two or more given integers without any remainder. We will discuss how to write an LCM program in Java. But before that let’s study some properties of LCM.

Properties of LCM

LCM follows the following properties.

• Associative: LCM (p, q) = LCM (q, p)
• Commutative: LCM (p, q, r) = LCM (LCM (p, q), r) = LCM (p, LCM (q, r))
• Distributive: LCM (kp, kq, kr) = kLCM (p, q, r)
• LCM of two or more numbers is always greater than or equal to the largest number.
• LCM of two or more co-prime numbers (numbers with no common factor other than 1) is equal to their product.

LCM Program in Java: Using while Loop if Statement

We can write an LCM program in Java from the basic definition that we have discussed above LCM is the smallest number that is divisible by both numbers.

Algorithm for LCM Program in Java: Using while Loop

The algorithm for finding LCM using the while loop is given below.

• Step 1: Declare two integers.
• Step 2: Find the maximum of the two numbers.
• Step 3: Use a while loop to check if the maximum number is divisible by both the given numbers.
• Step 4: If it is divisible, then it is the LCM.
• Step 5: If it is not divisible, increment the maximum number and repeat step 3.

Code for LCM Program in Java: Using while Loop

Here is the code implementation for the above-mentioned algorithm.

class PrepBytes{
    public static void main(String[] args) {
        int p = 18;
        int q = 24;
    	int lcm = 0;
    	
    	int max = (p > q) ? p : q;
      
    	while(true) {
        	if(max % p == 0 && max % q == 0) {
            	lcm = max;
            	break;
        	}
        	max++;
    	}
      
    	System.out.println("LCM is " + lcm);
    }
}

Output:

LCM is 72

LCM Program in Java: Using Prime Factorization

The LCM Program in Java is the naive approach. We can also find the LCM of two numbers by using prime factorization, the technique that we use way back in schools for finding the LCM of two numbers. In this method, we will find the prime factors of the given numbers and then multiply the common and uncommon factors to get the LCM.

Algorithm for LCM Program in Java: Using Prime Factorization

The algorithm for finding LCM using the prime factorization is given below in a step-wise manner.

• Step 1: Declare two integers.
• Step 2: Find the prime factors of both numbers.
• Step 3: Multiply the common prime factors with the highest power and uncommon prime factors to get the LCM.

Code for LCM Program in Java: Using Prime Factorization

Here’s the Java code for finding LCM using prime factorization.

class PrepBytes{
   public static void main(String[] args) {
    	int lcm = 1;
    	int i = 2;
      
    	int p = 18;
    	int q = 24;
    	
    	while(p != 1 || q != 1) {
        	if(p % i == 0 && q % i == 0) {
            	lcm *= i;
            	p /= i;
            	q /= i;
        	} else if(p % i == 0) {
            	lcm *= i;
            	p /= i;
        	} else if(q % i == 0) {
            	lcm *= i;
            	q /= i;
        	} else {
            	i++;
        	}
    	}
      
    	System.out.println("LCM is " + lcm);
   }
}

Output:

LCM is 72

LCM Program in Java: Using GCD

There is a relationship between GCD and LCM as shown in the image below.

In this method, we will find the GCD (Greatest Common Divisor) of the given numbers using Euclid’s algorithm and then use the above formula. For learning more about how to calculate GCD, follow this link – GCD of two numbers.

Algorithm for LCM Program in Java: Using GCD

The algorithm for the LCM program in Java is as follows:

• Step 1: Declare two integers.
• Step 2: Find the GCD of the two numbers using Euclid’s algorithm.
• Step 3: Use the formula LCM = (num1 * num2) / GCD(num1, num2) to get the LCM.

Code for LCM Program in Java: Using GCD

Here’s the Java code for finding LCM using GCD.

class PrepBytes {
    public static int findGCD(int a, int b) {
    	if(b == 0) return a;
        return findGCD(b, a % b);
    }
    
    public static void main(String[] args) {
    	int p = 18;
    	int q = 24;
      
    	int gcd = findGCD(p, q);
    	int lcm = (p * q) / gcd;
      
    	System.out.printf("LCM: " +  lcm);
   }
   
   
}

Output:

LCM: 72

LCM Program in Java: Using Multiples of Number

In this method, we will find the multiples of the given numbers and check for the common multiple to get the LCM.

Algorithm for LCM Program in Java: Using Multiples of Number

The algorithm is as follows:

• Step 1: Declare two integers.
• Step 2: Assign the value of the maximum between the two numbers to a variable.
• Step 3: Now run a for loop starting from a maximum of two numbers and the variable is incremented accordingly. Inside the loop, we continuously check whether the number is lcm or not.

Code for LCM Program in Java: Using Multiples of Number

Here’s the Java code for coding the LCM program in Java using multiples of numbers.

class PrepBytes {
    public static void main(String args[]) {
        int p = 18;
        int q = 24;
        int lcm;
        int temp = (p > q) ? p : q;

        for (lcm = temp; lcm <= p * q; lcm = lcm + temp) {
            if (lcm % p == 0 && lcm % q == 0)
                break;
        }
        
        System.out.println("The LCM is " + lcm);
    }
}

Output:

The LCM is 72

Conclusion
In this article, we have discussed the properties of LCM and various methods to write the LCM Program in Java. The methods include using while loop and if statements, prime factorization, GCD, and multiples of numbers. Each method has its advantages and disadvantages, and the choice of method depends on the given problem’s requirements.

Frequently Asked Questions(FAQs)

Here are some frequently asked questions on the LCM program in Java.

Ques 1. How do you calculate the LCM of three numbers in Java?
Ans. To calculate the LCM of three numbers in Java, you can either find the LCM of the first two numbers, and then find the LCM of that result and the third number, or you can use the prime factorization method.

Ques 2. Can you find the LCM of decimal numbers in Java?
Ans. No, the LCM can only be found for integers in Java.

Ques 3. What happens when you try to find the LCM of zero and any other number in Java?
Ans. If you try to find the LCM of zero and any other number in Java, the result will always be zero.