The Least Common Multiple (LCM) of two numbers is the smallest positive integer that is divisible by both numbers. This article will cover various methods to find the LCM of two numbers in C. We will explore multiple examples, each demonstrating a different approach to solve the problem.
Prerequisites
Before we delve into the examples, ensure you have the following prerequisites:
- A C compiler (such as GCC)
- A text editor or IDE for writing your C code
- Basic understanding of C programming concepts, especially loops and functions
1. Finding the LCM of Two Numbers
In this section, we will look at several methods to find the LCM of two numbers in C.
1.1 Using the Basic Formula
Example 1: Calculate LCM Using the Basic Formula
This method uses the basic formula for LCM is given by
\text{LCM}(a, b) = \frac{|a \times b|}{\text{GCD}(a, b)}Code
#include <stdio.h>
int gcd(int a, int b);
int main() {
int a, b, lcm;
printf("Enter two integers: ");
scanf("%d %d", &a, &b);
lcm = (a * b) / gcd(a, b);
printf("LCM of %d and %d is %d\n", a, b, lcm);
return 0;
}
int gcd(int a, int b) {
while (b != 0) {
int temp = b;
b = a % b;
a = temp;
}
return a;
}
Explanation
- Include necessary header:
#include <stdio.h>for input/output functions. - Declare a function to calculate GCD:
int gcd(int a, int b)to compute the GCD iteratively. - Input the numbers:
scanfreads two integers from the user. - Calculate LCM using the formula: Use the GCD function and the formula to find the LCM.
- Output the result:
printfdisplays the LCM of the two numbers.
Output
Enter two integers: 12 15
LCM of 12 and 15 is 60
1.2 Using the Iterative Method
Example 2: Calculate LCM Using the Iterative Method
This method uses iteration to find the LCM by incrementing the larger number until it is divisible by both numbers.
Code
#include <stdio.h>
int main() {
int a, b, lcm;
printf("Enter two integers: ");
scanf("%d %d", &a, &b);
lcm = (a > b) ? a : b;
while (1) {
if (lcm % a == 0 && lcm % b == 0) {
printf("LCM of %d and %d is %d\n", a, b, lcm);
break;
}
++lcm;
}
return 0;
}
Explanation
- Include necessary header:
#include <stdio.h>for input/output functions. - Input the numbers:
scanfreads two integers from the user. - Iterate to find LCM: Start with the larger number and increment it until it is divisible by both numbers.
- Output the result:
printfdisplays the LCM of the two numbers.
Output
Enter two integers: 4 6
LCM of 4 and 6 is 12
1.3 Using Recursion
Example 3: Calculate LCM Using Recursion
This method uses recursion to find the LCM by leveraging the relationship between GCD and LCM.
Code
#include <stdio.h>
int gcd(int a, int b);
int lcm(int a, int b);
int main() {
int a, b;
printf("Enter two integers: ");
scanf("%d %d", &a, &b);
printf("LCM of %d and %d is %d\n", a, b, lcm(a, b));
return 0;
}
int gcd(int a, int b) {
if (b == 0)
return a;
else
return gcd(b, a % b);
}
int lcm(int a, int b) {
return (a * b) / gcd(a, b);
}
Explanation
- Include necessary header:
#include <stdio.h>for input/output functions. - Declare recursive functions:
int gcd(int a, int b)for GCD andint lcm(int a, int b)for LCM. - Input the numbers:
scanfreads two integers from the user. - Calculate LCM using recursion: Use the GCD function and the formula to find the LCM.
- Output the result:
printfdisplays the LCM of the two numbers.
Output
Enter two integers: 7 5
LCM of 7 and 5 is 35
1.4 Using Prime Factorization
Example 4: Calculate LCM Using Prime Factorization
This method finds the LCM by using the prime factorizations of the two numbers.
Code
#include <stdio.h>
int gcdUsingPrimeFactors(int a, int b);
int main() {
int a, b;
printf("Enter two integers: ");
scanf("%d %d", &a, &b);
int lcm = (a * b) / gcdUsingPrimeFactors(a, b);
printf("LCM of %d and %d is %d\n", a, b, lcm);
return 0;
}
int gcdUsingPrimeFactors(int a, int b) {
int gcd = 1;
for (int i = 2; i <= a && i <= b; ++i) {
while (a % i == 0 && b % i == 0) {
gcd *= i;
a /= i;
b /= i;
}
}
return gcd;
}
Explanation
- Include necessary header:
#include <stdio.h>for input/output functions. - Declare a function to calculate GCD using prime factors:
int gcdUsingPrimeFactors(int a, int b). - Input the numbers:
scanfreads two integers from the user. - Calculate LCM using the formula: Use the GCD function and the formula to find the LCM.
- Output the result:
printfdisplays the LCM of the two numbers.
Output
Enter two integers: 8 14
LCM of 8 and 14 is 56
1.5 Using Arrays to Store Multiples
Example 5: Calculate LCM Using Arrays to Store Multiples
This method uses arrays to store multiples of the two numbers and find the LCM by comparing the arrays.
Code
#include <stdio.h>
int main() {
int a, b, lcm = 0;
int multiplesA[100], multiplesB[100];
printf("Enter two integers: ");
scanf("%d %d", &a, &b);
for (int i = 1; i <= 100; ++i) {
multiplesA[i-1] = a * i;
multiplesB[i-1] = b * i;
}
for (int i = 0; i < 100; ++i) {
for (int j = 0; j < 100; ++j) {
if (multiplesA[i] == multiplesB[j]) {
lcm = multiplesA[i];
break;
}
}
if (lcm != 0) break;
}
printf("LCM of %d and %d is %d\n", a, b, lcm);
return 0;
}
Explanation
- Include necessary header:
#include <stdio.h>for input/output functions. - Input the numbers:
scanfreads two integers from the user. - Store multiples in arrays: Use loops to fill arrays with multiples of the two numbers.
- Find common multiple: Compare the arrays to find the first common multiple.
- Output the result:
printfdisplays the LCM of the two numbers.
Output
Enter two integers: 6 8
LCM of 6 and 8 is 24
2. Conclusion
In this article, we explored various methods to calculate the LCM of two numbers in C: using the basic formula, using the iterative method, using recursion, using prime factorization, and using arrays to store multiples. Each method demonstrates different aspects of handling mathematical operations and implementing algorithms in C programming. By understanding these methods, you can choose the one that best fits your specific needs and enhance your skills in algorithm implementation and modular programming in C.