C++ Program to Find LCM

Examples on different ways to calculate the LCM (Lowest Common Multiple) of two integers using loops and decision making statements.

To understand this example, you should have the knowledge of the following C++ programming topics:

C++ if, if...else and Nested if...else
C++ while and do...while Loop

LCM of two integers a and b is the smallest positive integer that is divisible by both a and b.

#include <iostream>
using namespace std;

int main()
{
int n1, n2, max;

cout << "Enter two numbers: ";
cin >> n1 >> n2;

// maximum value between n1 and n2 is stored in max
max = (n1 > n2) ? n1 : n2;

do
{
if (max % n1 == 0 && max % n2 == 0)
{
cout << "LCM = " << max;
break;
}
else
++max;
} while (true);

return 0;
}

Output

Enter two numbers: 12
18
LCM = 36

https://www.toysruscreditcard.net/
Last edited on
?? and the purpose of this is?? In C++17 there's the std::lcm() function to do this. As well as gcd().

Using this basic algorithm, coded as:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <iostream>

int main()
{
	int n1 {}, n2 {};

	std::cout << "Enter two numbers: ";
	std::cin >> n1 >> n2;

	auto max {(n1 > n2) ? n1 : n2};

	for (; max % n1 != 0 || max % n2 != 0; ++max);

	std::cout << "LCM = " << max << '\n';
}


A better algorithm would be to use gcd

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>

int gcd(int a, int b) {
	return b == 0 ? a : gcd(b, a % b);
}

int lcm(int a, int b) {
	return (a * b) / gcd(a, b);
}

int main() {
	int n1 {}, n2 {};

	std::cout << "Enter two numbers: ";
	std::cin >> n1 >> n2;

	std::cout << "LCM = " << lcm(n1, n2) << '\n';
}


But again - why?? as C++ now has these functions.
But again - why?? as C++ now has these functions.


Maybe because it's a good exercise for students?

Most students who are learning C++ should know what a GCD or an LCM is. And working through the math needed to calculate them is a no-trivial but not extremely complex homework assignment.
is a no-trivial but not extremely complex homework assignment.


Very trivial - as the code for them are all over the internet! :)
I agree it's a nice exercise for students. Although the O(log n) algorithm is very clever and not something a typical student would come up with on his or her own; most students just do the O(n) version and call it a day (e.g. Fraction classes).
Last edited on
Topic archived. No new replies allowed.