C语言辗转相除法问题

#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;iscanf("%d",&a[i]);
res = fun(a[0],a[1]);
for(i=2;ires = fun(res,a[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，并返回第一步。

#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 scanf("%d",&a[i]);
res = fun(a[0],a[1]);
for(i=2;i res = fun(res,a[i]);
printf("%d\n",res);

return 0;
}

#include
void swap(int *a,int *b)
{
int t;
t=*a;
*a=*b;
*b=t;
}
int fun(int a,int b)
{
int t;
while(a%b!=0)
{
t=b;
b=a%b;
a=t;
}
return b;
}
main()
{
int a,b;
scanf("%d",&a);
while(1)
{
scanf("%d",&b);
if(b==0)
break;
if(a swap(&a,&b);
a=fun(a,b);
}
printf("%d",a);
}

以0作为输入结束的标志

#include
void main()
{
int a, b, x, y, temp;
x = 34; y = 12;
if(x < y)
{
temp = x; x = y; y = temp;
}
a = x; b = y;
while(b != 0)
{
temp = a % b;
a = b;
b = temp;
}
printf("yue:%d\n", a);
}