lowest common multiple

[areenlaz]

i want to write a program that calculates the lowest common multiple for two integer numbers that inputs by user
and show results at screen.
thanks

[anup30]

one way is by mathematical method,
if you dont know that,
suppose, input is x and y.
x<y
then 2x%y == 0 ?
3x%y == 0 ?
.
.
.
go until you find

[rjvc]

hmm...you can try dividing it with 2 or 3(and odd numbers) until they cannot be divided anymore(see http://www.mathsisfun.com/prime-factorization.html). Then get the values which are unique and highest common values(say 2^1 and 2^2) then multiply them and the result would be the LCM.

[dhayden]

To get LCM, first compute the greatest common factor (GCF). Then if the numbers are A and B, the LCM = A*B/GCF(A,B)

[anup30]

To get LCM, first compute the greatest common factor (GCF). Then if the numbers are A and B, the LCM = A*B/GCF(A,B)

thats invalid for 3 or more numbers.

the easiest method comes to my mind (let cpu do the hardwork) :

  int A, B, C;
  cin >> A >> B >> C;
  int i =A;
  while(true)
  {
  	if (i%B==0 && i%C==0)
  	  break;
  	i+=A;  
  }
  
  cout << "LCM = " << i << endl;

[dhayden]

thats invalid for 3 or more numbers.

The problem statement was for 2 numbers. Even so, the extension is pretty simple since LCM(a,b,c) = LCM(a, (LCM(b,c)), so you just repeat the process.

More importantly, GCF is fast: O(log(N)) I think. So with M numbers whose max size is N, my algorithm is O(M*log(N)) whereas yours is O(N^M).

[anup30]

as i mentioned earlier, i focused on programmers ease. you on CPU's ease. but, there is faster method than you showed.

[Smac89]

There is a method for finding the lcm of numbers which makes use of prime factorization