What is LCM (Least Common Multiple)? LCM stands for Least Common Multiple. It is a method to find the lowest common multiple between the two numbers. LCM of two numbers is the lowest possible number that is divisible by both numbers. Examples: LCM(10,15) = 30, LCM(18,26) = 234. Write a C program to find the LCM of two numbers. 1. Take two numbers as input. 2. Find the maximum of the two numbers. 3. If the maximum is completely divisible by both the numbers return the maximum as output. 4. Else keep on increasing the maximum one by one until it is completely divisible by both the numbers. 5. Finally return the new value of the maximum. There are several ways to find the LCM of two numbers in C language. Let’s look at the three different techniques to write a C program to calculate the LCM of two numbers. Method 1: LCM of Two Numbers in C using While Loop In this approach, we find the LCM of two numbers using a while-loop
Subscribe Now: C Programs Newsletter | Important Subjects Newsletters Here is the source code of the C program to find the LCM of two numbers using while loop. The C program is successfully compiled and run on a Linux system. The program output is also shown below. /* * C program to find LCM of two numbers */ #include<stdio.h> void main() { int a, b, max; printf("Enter the two numbers : "); scanf("%d %d", &a, &b); max = (a > b) ? a : b; // maximum number between a and b is stored in max while (max % a != 0 || max % b != 0) { max++; } printf("The LCM of %d and %d is %d.", a, b, max); } 1. Take the two numbers a and b as input. Example:
Become Top Ranker in C Programming Now!
Time Complexity: O(n) Space Complexity: O(1) Testcase 1: The numbers entered by the user to calculate lcm in this case are 2 and 5. Enter the two numbers: 2 5 The LCM of 2 and 5 is 10. Testcase 2: The numbers entered by the user to calculate lcm are 12 and 15. Enter the two numbers: 12 15 The LCM of 12 and 15 is 60. Method 2: LCM of Two Numbers in C using Recursion In this approach, lcm() function is used to find the LCM of two numbers using recursion. Here is the source code of the C program to find the LCM of two numbers using recursion. The C program is successfully compiled and run on a Linux system. The program output is also shown below.
1. In this C program, we are reading the two integer numbers using ‘a’ and ‘b’ variables respectively. Example:
Time Complexity: O(n) The above program to find the LCM of two numbers has a time complexity of O(n), because the recursion is called many times until the LCM is found, where n = LCM of the two numbers. Since the LCM is calculated using the common variable and the common variable starts from 1. Space Complexity: O(1) Testcase 1: The numbers entered by the user to find the lcm in this case are 2 and 3. Enter the two numbers: 2 3 The LCM of 2 and 3 is 6. Testcase 2: The numbers entered by the user to calculate lcm are 12 and 15. Enter the two numbers: 12 15 The LCM of 12 and 15 is 60. Method 3: LCM of Two Numbers in C using GCD In this approach, we find the LCM of two numbers using GCD (Greatest Common Divisor). Here is the source code of the C program to find the LCM of two numbers using GCD. The C program is successfully compiled and run on a Linux system. The program output is also shown below. /* * C program to find the LCM of two numbers using GCD */ #include<stdio.h> void main() { int num1, num2, gcd, lcm, remainder, numerator, denominator; printf("Enter two numbers\n"); scanf("%d %d", &num1, &num2); if (num1 > num2) { numerator = num1; denominator = num2; } else { numerator = num2; denominator = num1; } remainder = numerator % denominator; while (remainder != 0) { numerator = denominator; denominator = remainder; remainder = numerator % denominator; } gcd = denominator; lcm = (num1 * num2) / gcd; printf("LCM of %d and %d = %d\n", num1, num2, lcm); } 1. In this C program, we are reading the two integer numbers. Example:
Time Complexity: O(log(min(a,b))) Space Complexity: O(1) Testcase 1: The numbers entered by the user to calculate lcm in this case are 2 and 3. Enter the two numbers: 12 15 The LCM of 12 and 15 is 60. Testcase 2: The numbers entered by the user to calculate lcm are 12 and 15. Enter the two numbers: 7 2 The LCM of 7 and 2 is 14. To practice programs on every topic in C, please visit “Programming Examples in C”, “Data Structures in C” and “Algorithms in C”. Next Steps:
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn. Subscribe to his free Masterclasses at Youtube & technical discussions at Telegram SanfoundryClasses. |