求兩個或N個數的最大公約數(gcd)和最小公倍數(lcm)的較優算法

#include <iostream>
#include <cmath>
using namespace std;

int gcd(int a, int b);
int ngcd(int *a, int n);
int lcm(int a, int b);
int nlcm(int *a, int n);

int main()
{
 //int a,b;
 //cin >> a >> b;
 //cout << lcm(a, b) << endl;
 int *a = new int[3];
 a[0] = 3;
 a[1] = 4;
 a[2] = 5;
 cout << nlcm(a, 3) << endl;

 return 0;
}

//兩個數的最大公約數--歐幾里得算法
int gcd(int a, int b)
{
 if (a < b)
  swap(a, b);

 if (b == 0)
  return a;
 else
  return gcd(b, a%b);
}

//n個數的最大公約數算法
//說明:
//把n個數保存為一個數組
//參數為數組的指針和數組的大小(需要計算的數的個數)
//然后先求出gcd(a[0],a[1]), 然后將所求的gcd與數組的下一個元素作為gcd的參數繼續求gcd
//這樣就產生一個遞歸的求ngcd的算法
int ngcd(int *a, int n)
{
 if (n == 1)
  return *a;

 return gcd(a[n-1], ngcd(a, n-1));
}

//兩個數的最小公倍數(lcm)算法
//lcm(a, b) = a*b/gcd(a, b)
int lcm(int a, int b)
{
 return a*b/gcd(a, b);
}

//n個數的最小公倍數算法
//算法過程和n個數的最大公約數求法類似
//求出頭兩個的最小公倍數,再將欺和大三個數求最小公倍數直到數組末尾
//這樣產生一個遞歸的求nlcm的算法
int nlcm(int *a, int n)
{
 if (n == 1)
  return *a;
 else
  return lcm(a[n-1], nlcm(a, n-1));
}