LCM Program Method 2 in Java and Python
LCM Method 2 program with algorithm, explanation, Java solution and simple Python solution for ICSE and ISC students.
Question:
Write a program to find the Least Common Multiple (L.C.M.) of two numbers entered by the user.
Note: This is the second method of finding the L.C.M. of two numbers. In this method, the program checks multiples of the greater number instead of checking every number one by one. The first method can be read here: LCM Method 1.
Algorithm:
Step 1: Start.
Step 2: Accept two numbers a and b from the user.
Step 3: Compare a and b to find the greater number and store it in max.
Step 4: Store the smaller number in min.
Step 5: Initialize lcm to 1.
Step 6: Run a loop with counter i from 1 to min.
Step 7: In every pass, calculate x = max * i. This gives the next multiple of the greater number.
Step 8: Check whether x % min == 0.
Step 9: If the condition is true, store x in lcm and stop the loop because the first such multiple is the least common multiple.
Step 10: Display lcm.
Step 11: Stop.
Explanation:
The Least Common Multiple of two numbers is the smallest number that is exactly divisible by both of them. The first method of finding LCM usually checks every number from one of the given numbers up to the product of both numbers. This second method reduces unnecessary checking by using a better observation: the LCM must be a multiple of the greater number.
The program first compares the two input numbers and stores the greater value in max and the smaller value in min. This is useful because the loop does not need to test all ordinary numbers. It only generates multiples of max. For example, if the numbers are 336 and 224, the possible values checked are 336, 672, 1008 and so on. Values such as 337, 338 and 339 are ignored because they cannot be multiples of 336.
Inside the loop, the statement x = max * i produces the next multiple of the greater number. The program then checks whether this multiple is also divisible by the smaller number using x % min == 0. If the remainder is zero, then x is a common multiple of both numbers. Since the multiples are generated in increasing order, the first common multiple found is automatically the least common multiple. Therefore the loop stops immediately using break.
This method is more efficient because it checks only multiples of one number, not every integer in the range. For the sample input 336 and 224, Method 1 may examine many values before reaching 672, but this method reaches 672 in only the second multiple of 336. The logic remains simple enough for ICSE and ISC students while showing a clear improvement in loop efficiency.
Java Program:
/**
* The class LcmMethod_2 takes two numbers as input and finds their LCM.
* This is Method 2.
* @author : www.guideforschool.com
* @Program Type : BlueJ Program - Java
*/
import java.util.Scanner;
class LcmMethod_2
{
public static void main(String args[])
{
Scanner sc = new Scanner(System.in);
System.out.print("Enter the first number: ");
int a = sc.nextInt();
System.out.print("Enter the second number: ");
int b = sc.nextInt();
int max, min;
int x;
int lcm = 1;
// Store the greater number in max and the smaller number in min.
if(a > b)
{
max = a;
min = b;
}
else
{
max = b;
min = a;
}
/*
* The LCM must be a multiple of the greater number.
* So only multiples of max are generated and tested.
*/
for(int i = 1; i <= min; i++)
{
x = max * i; // Generate the next multiple of the greater number.
if(x % min == 0) // Check whether the same value is also divisible by min.
{
lcm = x; // The first such value is the least common multiple.
break;
}
}
System.out.println("L.C.M. = " + lcm);
}
}Equivalent Python Program:
a = int(input("Enter the first number: "))
b = int(input("Enter the second number: "))
# Store the greater number in max_num and the smaller number in min_num.
if a > b:
max_num = a
min_num = b
else:
max_num = b
min_num = a
lcm = 1
# Generate only multiples of the greater number.
for i in range(1, min_num + 1):
x = max_num * i
# The first multiple also divisible by min_num is the LCM.
if x % min_num == 0:
lcm = x
break
print("L.C.M. =", lcm)Output:
Leave a Reply
Your email address will not be published. Comments are reviewed before appearing publicly.