辗转相除法的算法步骤为,两个数中用较大数除以较小数,再用出现的余数(第一余数)去除除数。
再用出现的余数(第二余数)去除第一余数,如此反复,直到最后余数是0为止。得到最后的除数就是这两个数的最大公约数。
扩展资料:
扩展欧几里得算法可用于RSA加密等领域。
假如需要求 1997 和 615 两个正整数的最大公约数,用欧几里得算法,是这样进行的:
1997 / 615 = 3 (余 152)
615 / 152 = 4(余7)
152 / 7 = 21(余5)
7 / 5 = 1 (余2)
5 / 2 = 2 (余1)
2 / 1 = 2 (余0)
至此,最大公约数为1
用辗转相除法(即欧几里得算法)求两个正整数的最大公约数.解析:
设两个数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=8n=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的值
源程序:
#include
void main()
{
int m,n,q,a,b
printf("Enter two integers:")
scanf("%d%d",&a,&b)
m=a
n=b
if(n>m)
{
int z
z=mm=nn=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)
}
希望对你有所帮助!
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)