求两个数或者N个数的最大公约数和最小公倍数

我用的办法，应该算是简单粗暴的方法吧，时间复杂度是O（n），但是中间调用了N-1一次函数，效率估计不会很高。

求最大公约数的首先是求前两个数的最大公约数，用辗转相除法，然后将这个最大公约数max_cd和第三个数求最大公约数的，

然后和第三个数求得的最大公约数继续和第四个数求最大公约数，知道第N个数。

最小公倍数也是如此，先求前两个数的最小公倍数 min_cd，然后将min_cd和第三个数求最小公倍数，直到第n个数。

至于为什么能这样算，我是没有严格证明的，只是通过经验觉得可以这样。

ps:由于笔者水平有限，如有错误或者更好的解法，还望各位道友多多帮忙。

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

/*
求两个数以及N个数的最大公约数和最小公倍数
输入值仅能为正整数，不进行输入错误判断及处理
*/

//求两个数的最大公约数
int  maxGCD( int a , int b)
{
int temp;
if(a<b)
{
temp=a;
a=b;
b=temp;
}

//辗转相除法求最大公约数，不知道这个方法的可以自行百度
temp=a%b;
while(temp!=0)
{
a=b;
b=temp;
temp=a%b;
}

return b;
}

int main()
{
//p 用于存储输入的N个数
int *p;
int max_cd;
int min_cd;
int n;

scanf("%d",&n);

p = (int *) malloc ( n*sizeof(int));

for(int i=0;i<n;i++)
scanf("%d",p+i);

//求n个数的最大公约数
//先求前面两个数的最大公约数
max_cd=maxGCD( *p, *(p+1) );
for(int i=2; i<n; i++)
{
max_cd=maxGCD( max_cd , *(p+i));
}

//求最小公倍数
min_cd=(*p)*(*(p+1))/maxGCD( *p, *(p+1));
for( int i=2; i<n; i++)
{
min_cd=min_cd*(*(p+i))/maxGCD( min_cd , *(p+i));
}

printf("%d %d \n",max_cd, min_cd);
 getchar();
return 0;
}