C Program to Find LCM of Two Numbers
C Program to Find LCM of Two Numbers
Two school clubs meet every twelve and eighteen days. Find the first positive day when their repeating schedules meet again.
For positive integers, the least common multiple is a divided by gcd(a,b), then multiplied by b.
Before this exercise, review loops and stopping conditions and functions and parameters. The worked program below applies those ideas to this specific problem.
Explain
Explain why least common multiple uses this sequence of operations.
Trace
Trace the sample values and predict the printed result.
Apply
Use club periods four and six.
Least Common Multiple: follow the data
Given data
Two school clubs meet every twelve and eighteen days. Find the first positive day when their repeating schedules meet again.
Rule
For positive integers, the least common multiple is a divided by gcd(a,b), then multiplied by b.
Observed result
LCM: 36
Understand the operation
The Euclidean algorithm repeatedly replaces a pair with its second value and the division remainder until the remainder is zero. The remaining first value is the greatest common divisor.
Divide before multiplying to reduce the intermediate product. This reduces overflow risk but does not prove that the final least common multiple fits its type.
Read the complete C program
The input values are written into this complete C17 example so the calculation can be reproduced without an unavailable service. Change the named data, rebuild and compare the actual output with your prediction.
C17 · complete program
#include <stdio.h>
static unsigned gcd(unsigned a, unsigned b) {
while (b != 0) { unsigned remainder = a % b; a = b; b = remainder; }
return a;
}
int main(void) {
unsigned a = 12, b = 18;
unsigned result = (a / gcd(a, b)) * b;
printf("LCM: %u\n", result);
return 0;
}
Expected output
LCM: 36
Follow the values through the code
C17 · code used in this explanation
#include <stdio.h>
static unsigned gcd(unsigned a, unsigned b) {
while (b != 0) { unsigned remainder = a % b; a = b; b = remainder; }
return a;
}
int main(void) {
unsigned a = 12, b = 18;
unsigned result = (a / gcd(a, b)) * b;
printf("LCM: %u\n", result);
return 0;
}
The pairs for gcd(12,18) become (18,12), (12,6) and (6,0).
The gcd is six, so (12 / 6) × 18 gives 36.
Follow the worked calculation
Start with the sample
The pairs for gcd(12,18) become (18,12), (12,6) and (6,0).
Apply the rule
The gcd is six, so (12 / 6) × 18 gives 36.
Check the result
LCM: 36
LCM: 36
Try a small variation
C17 · code used in this explanation
#include <stdio.h>
static unsigned gcd(unsigned a, unsigned b) {
while (b != 0) { unsigned remainder = a % b; a = b; b = remainder; }
return a;
}
int main(void) {
unsigned a = 12, b = 18;
unsigned result = (a / gcd(a, b)) * b;
printf("LCM: %u\n", result);
return 0;
}
Use club periods four and six.
Worked answer
The gcd is two. Dividing four by two and multiplying by six gives twelve, the first positive shared meeting interval.
C17 · complete program
#include <stdio.h>
static unsigned gcd(unsigned a, unsigned b) {
while (b != 0) { unsigned remainder = a % b; a = b; b = remainder; }
return a;
}
int main(void) {
unsigned a = 4, b = 6;
unsigned result = (a / gcd(a, b)) * b;
printf("LCM: %u\n", result);
return 0;
}
Expected output
LCM: 12
Recognize the important boundaries
This program’s contract is two positive small unsigned integers. If you allow zero, handle it before dividing by gcd, especially when both values are zero.
Before the final multiplication, compare the reduced factor with the representable maximum divided by b for a general checked implementation.
Check your understanding
Choose the answer, then compare the reasoning for every option.
Use the idea independently
For positive integers, the least common multiple is a divided by gcd(a,b), then multiplied by b.
Continue with testing the problem’s boundary cases.
Language reference: WG14 C11 committee draft. These examples use the C17-compatible subset of the explained language features.
Reaching the recap and completing the quizzes are separate milestones.