首页 > 代码库 > 求N个数的最大公约数

求N个数的最大公约数

 

#include <stdio.h>
#include <assert.h>
#define N 100
int gcd(int x,int y)
{
    int t;
    if(x<y)
    {
        t=x;
        x=y;
        y=t;
    }
    return (y==0)?x:gcd(y,x%y); 
}
int ngcd(int *p, int k)
{
    if (k == 1)
        return *p;
     return gcd(p[k-1],ngcd(p, k-1));
}
void main()
{
    int i,n,a[N];
    int result;
    scanf("%d",&n);
    for(i=0;i<n;i++)
    {
        scanf("%d",&a[i]);
    }
    result=ngcd(a,n);
    printf("%d\n",result);
    getchar();
    getchar();
}
View Code

除了递归,也可以用循环来实现,核心代码如下:

g = data[0];
    for(i = 1; i < n; ++i)
        g = gcd(g, data[i]);
View Code