Thread: Finding LCM--Driving me nuts

I am having the hardest time finding the lowest common denominator.
I have it set up in a for loop, for the life of me I can't find whats wrong.
Here is what I have so far:

Code:

for (x=0;x == LCM;++x)
		{
			var1 = x * denom1;  
			var2 = x * denom2;             
                        cout <<var1 <<"        " <<var2 <<endl;
                        if (var2 == var1)
                        {
                         x = LCM;
                         LCM = var1;
                        cout <<"The LCM is " <<LCM <<endl;
                       }
		}

It doesn't even seem like the for loop is finishing. It doesn't even cout the cout statment, it just continues with the rest of the program.

>>It doesn't even seem like the for loop is finishing. It doesn't
even cout the cout statment, it just continues with the rest of the
program.

It would appear that your logic is way out, because you didn't
even state the observed behavior properly - how can the loop
appear to never end AND continue with the program without
writing to the console?

My initial guess is that value of the LCM variable at the start of the
program has some silly value, but even still, how is this supposed
to be determining the LCM?

Code:

var1 = x * denom1;
var2 = x * denom2;
cout <<var1 <<"        " <<var2 <<endl;
if (var2 == var1)
{

Naturally, x is constant over these few lines of code, so how
exactly do you expect multiplying denom1 and denom2 by
x to change the the comparison test between var1 and var2?
basically those lines may as well simplify to:

if (denom1 == denom2)

To get really basic, look at this:

Code:

#include <iostream>

using namespace std;

int main (void)
{
	int denom1 = 1;
	int denom2 = 2;
	int var1, var2, x;

	for (x = 1; x <= 10; x++)
	{
		cout << "Denom1 = " << denom1 << " Denom2 = " << denom2 << endl;

		var1 = denom1 * x;
		var2 = denom2 * x;

		cout << "Var1 = " << var1 << " Var2 = " << var2 << endl << endl;
	}

	cout << "So Denom1 is always less than Denom 2, accordingly Var1 is always less than" << endl;
	cout <<"Var2" << endl;

	return 0;
}

Here's what Wikipedia has on LCM, take a look at the greatest
common divisor (GCD) too

I suggest you go back to the drawing board and try implementing
the algorithm again.

LCM
...
lowest common denominator

The easiest way to get the LCM: LCM is "least common multiple". So you start checking every number from 1 onwards until you find a number divisible by both X and Y. This is, by definition, the LEAST common multiple, since if there was a smaller one, you would have found it already. You will always find an LCM, because the largest possible value is X*Y.

The faster and better way to get the LCM: Note that LCM(X,Y) == X*Y / GCD(X,Y). There is already a fast and easy algorithm to get the GCD -- check Richie T's link.


Don't start coding yet... find out exactly what the problem is, and plan a way to solve it, before you actually put the thought into code.