Solved

# Finding lowest common multiple / highest common factor

Posted on 2001-06-21

I've got these two functions, homegrown obviously, which find the lowest common multiple of two numbers (or least common denominator for two fractions, for example 3 and 6 would be 3) and the highest common factor of two numbers (for example, 15 and 10 would be 5).

void CProblem::SolveFindHCF (__int64 n1, __int64 n2, __int64 *hcf)

{ __int64 i, range;

if (n1 <= -1)

{ n1 *= -1; }

if (n2 <= -1)

{ n2 *= -1; }

*hcf = 1;

if (n1 > n2)

{ range = n2; }

else

{ range = n1; }

for (i = 1; i <= range; i++)

{ if (n1 % i == 0 && n2 % i == 0)

{ *hcf = i; }

}

}

void CProblem::SolveFindLCD (__int64 n1, __int64 n2, __int64 *lcd)

{ __int64 tden, bden;

for (tden = n1; tden < n1 * 10000; tden += n1)

{ for (bden = n2; bden <= tden; bden += n2)

{ if (tden == bden)

{ *lcd = tden; // That's that

return;

}

}

}

}

The problem is the speed. When using large numbers, these functions are very slow. I would like tips on improving the speed of these functions. Sometimes millions of iterations are necessary for any given problem, and this is unacceptable as anyone with half a brain could realize.

Please post ways to enhance the performance and eliminate any bugs in these functions. Whoever contributes the most will get the points. Thanks!