CareerCup

I have a solution that doesn't require any prime test. Basically note that

LCM (a, b, c) = LCM(LCM (a, b), c)

This is easy to prove: basically LCM(a, b) takes the maximum index in the prime factorization of a, b. LCM(a, b, c) takes the maximum index of all possible primes in a, b, and c, which is equivalent to finding the maximum index of primes from a, b and then c.

Based on these, and the fact that LCM(a, b) = a * b / GCD(a, b), we can do an iterative algorithm that only requires a GCD procedure, which can be easily done using the Euclid's algorithm.

int GCD(int a, int b){
    if(b==0) return a;    
    return GCD(b, a%b);
}

int LCM(int a, int b){
    return a*b/GCD(a,b);
}

int LCM2(int *a, int i, int n){
    if(i == n){
        return 1;
    }
    
    return LCM(a[i],LCM2(a,i+1,n));
}

int a[] = {3,5,2};
LCM2(a,0,3) will be the call.

LCM = product of number/GCD
use it for all numbers

@Kishore: LCM is 90 for your example. I got similar kind of idea after looking your approach.
1. Minheapify the array.
2. Divide all the elements of array till first element becomes 1 at the same time maintain count for all prime divisors.
3. exchange 1st element to last and decrease array size.
4. if array size is is not zero go to 1 else stop.
So after step 1 - 4 if we have count n1,n2,n3 for primes p1,p2,p3 then the LCM is
LCM=p1*p1*..n1times * p2*p2*..n2 times, p3*p3*...n3times.
e.g.
Array = 10, 9 15, size is 3.

step 1 9,10,15 size 3 prime divisor none
step 2 3,10,5 size 3 prime divisors 3-->1
step 2 1,10,5 size 3 prime divisors 3-->2
step 3 5,10,1 size 2 prime divisors 3-->2
step 4 go to 1.

step 1 5,10,1 size 2 prime divisors 3-->2
step 2 1,2,1 size 2 prime divisors 3-->2 5-->1
step 3 2,1,1 size 1 prime divisors 3-->2 5-->1
step 4 go to 1

step 1 2,1,1 size 1 prime divisors 3-->2 5-->1
step 2 1,1,1 size 2 prime divisors 3-->2 5-->1 2-->1
step 3 1,1,1 size 0
step 4 STOP

LCM = 3*3*2*5 = 90

Test

Based on Eric Xu's comment:

#include <stdio.h>
#include <stdlib.h>
#include <vector>

unsigned int gcd(unsigned int a, unsigned int b)
{
  while(a != 0 && b != 0)
  {
    if (a > b) {
      a -= b;
    } else {
      b -= a;
    }
  }
  return a + b;
}

unsigned int lcm(std::vector<unsigned int>&num)
{
  if (num.empty())
  {
    printf("unable to calculate LCM for empty vector\n");
    exit(1);
  }
  else if (num.size() == 1)
  {
    return num.back();
  }
  else
  {
    unsigned int a = num.back();
    num.pop_back();
    unsigned int b = num.back();
    num.pop_back();
    unsigned int x = a * b / gcd(a, b);
    num.push_back(x);
    return lcm(num);
  }
}

int main()
{
  std::vector<unsigned int>num;
  num.push_back(10);
  num.push_back(9);
  num.push_back(15);
  printf("%d\n", lcm(num));
}

Here is an iterative version based on Xu's comment, also would it be a little faster if mod-based GCD computation is used instead of subtraction-based?

int GetGCD(int a, int b) {
     int aa = a;
     int bb = b;
     while (bb != 0) {
          int tmp = bb;
          bb = aa % bb;
          aa = tmp;
     }
     return aa;
}

int main(int argc, char** argv) {
  int array[3] = {10,9,15};
  vector<int> A(array, array+3);
  int n = A.size();
  int lcm;
  int left_operand = A[0];
  for (int i = 1; i < n; ++i) {
     int prod = left_operand * A[i];
     int gcd = GetGCD(left_operand, A[i]);
     lcm = prod / gcd;
     left_operand = lcm;
  }
  return lcm;
}

have a simple code for LCM

#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>

void main()
{
int i=2,j,n,*num,ct=0,lcm;
printf("Enter the total no:");
scanf("%d",&n);
if(n==0)
{
printf("Total no should be more then ZERO");
getch();
exit(1);
}
num=(int *)malloc(n*2);
for(i=0;i<=n-1;i++)
{
printf("enter the %d number:",i+1) ;
scanf("%d",&num[i]);
}
i=2;
while(i)
{
for(j=0,ct=0;j<=n-1;j++)
{
if(i%num[j]==0)
ct=ct+1;
}
if(ct==n)
{
lcm=i;
break;
}
i++;
}
printf("\nlcm=%d",lcm);
}

int LCM(int d,int e)
{
int a=d,b=e,c,lcm;
while((a=a%b)!=0)
{
c=a;
a=b;
b=c;
}
lcm=(d*e)/b;
return lcm;
}

in main function()
{
for(i=2;i<b;i++)
lcm=LCM(lcm,a[i]);


}

@vicky its complexity would be something like nlogn considering the while loop in LCM()

{{ karmaandcoding.blogspot.com /2011/03/lcm-of-array-of-numbers_16.html }}}

Does anybody know a more efficient solution?

def gcd(a, b):
    if b > a: a, b = b, a
    while a % b:
        a, b = b, a % b
    return b

def lcm(a, b):
    return a * b / gcd(a, b)

seq = [1, 2, 4, 8, 7]
lcm_tmp = lcm(seq[0], seq[1])
for i in range(2, len(seq)):
    lcm_tmp = lcm(lcm_tmp, seq[i])
print lcm_tmp

Nothing new same solution has been proposed earlier.

int gcd(int a, int b)
{
	int temp;

	while (a%b != 0) {
		temp = a%b;
		a = b;
		b = temp;
	}

	return b;
}
int lcm(int *a, int n)
{
	int result = 1;
	int i;
	for (i = 0; i < n; ++i) {
		result = (result/gcd(result, a[i])) * a[i];
	}

	return result;
}