#include
int fun(int a,int b) /* 2个数的公约数 */
{
int t;
while(b)
{
t = a%b;
a = b;
b = t;
}
return a;
}
int main()
{
int a[100];
int n;
int i;
int res;
scanf("%d",&n); /* 先输入数的总数n */
if(n < 2)
{
printf("n不能小于2\n");
return 0;
}
for(i=0;i
res = fun(a[0],a[1]);
for(i=2;i
printf("%d\n",res);
return 0;
}
欧几里德算法又称辗转相除法，用于计算两个正整数a，b的最大公约数。
其计算原理依赖于下面的定理：
定理：gcd(a,b) = gcd(b,a mod b) (a>b 且a mod b 不为0)
证明：a可以表示成a = kb + r，则r = a mod b
辗转相除法是利用以下性质来确定两个正整数 a 和 b 的最大公因子的：
⒈ 若 r 是 a ÷ b 的余数，且r不为0， 则
gcd(a,b) = gcd(b,r)
⒉ a 和其倍数之最大公因子为 a。
另一种写法是：
⒈ 令r为a/b所得余数（0≤r
若 r= 0，算法结束；b 即为答案。
⒉ 互换：置 a←b，b←r，并返回第一步。
内容全部来源于网络收集，如有侵权，请联系网站删除：QQ：24596024