辗转相除法c语言函数,c语言辗转相除法原理

C语言辗转相除法

例如用辗转相除法求a b 最大公约数（a b谁大谁小无所谓）：

创新互联建站是一家专注于成都做网站、网站制作与策划设计,乌当网站建设哪家好?创新互联建站做网站,专注于网站建设十余年,网设计领域的专业建站公司;建站业务涵盖:乌当等地区。乌当做网站价格咨询:028-86922220

int GCD( int a , int b )

{

int n=a%b;

whie(n != 0) //即： while(n)

{

a = b;

b = n;

n = a % b;

}

return b; //注意这里返回的是b 不是n

}

辗转相除法c语言代码

辗转相除法用来求两个数的最大公约数，代码如下：

#include stdio.h

#include stdlib.h

int main()

{

int a, b,r;

scanf("%d %d", a, b);

while(b!=0)//当其中一个数为0，另一个数就是两数的最大公约数

{

r = a%b;

a = b;

b = r;

}

printf("Greatest Common Divisor: %d\n", a);

system("pause");

}

运行结果：

什么是c语言里面的辗转相除法

用辗转相除法（即欧几里得算法）求两个正整数的最大公约数。

解析：

设两个数m,n，假设m=n，用m除以n，求得余数q。若q为0，则m为最大公约数；若q不等于0，则进行如下迭代：

m=n,n=q,即原除数变为新的被除数，原余数变为新的除数重复算法，直到余数为0为止。余数为0时的除数n，即为原始m、n的最大公约数。

迭代初值：m，n的原始值；

迭代过程：q=m%n;

m=n;

n=q;

迭代条件：q!=0

例如：m=8;n=6

q=m%n(8%6==2)

m=n(m==6)

n=q(n==2)

因为：(q==2)!=0，重复算法：

q=m%n(6%2==0)

m=n(m==2)余数为0时的除数n为最大公约数，n值赋给了m，所以输出m的值

n=q(n==0)

因为：q==0 所以最大公约数为m的值

源程序：

#includestdio.h

void main()

{

int m,n,q,a,b;

printf("Enter two integers:");

scanf("%d%d",a,b);

m=a;

n=b;

if(nm)

{

int z;

z=m;m=n;n=z;//执行算法前保证m的值比n的值大

}

do

{

q=m%n;

m=n;

n=q;

}while(q!=0);

printf("The greatest common divisor of");

printf("%d,%d is %d\n",a,b,m);

}

希望对你有所帮助!