欧几里德算法
来源：爱站网时间：2020-11-09编辑：网友分享
欧几里德是辗转相除法，是我们在C语言中经常需要使用到的一种算法，那么你知道怎么使用欧几里德算法吗？
欧几里德是辗转相除法，是我们在C语言中经常需要使用到的一种算法，那么你知道怎么使用欧几里德算法吗？
首先看递归实现：
int getcd(int m,int n)
{
if (m return 0;
}
if(m {
int t = m;
m = n;
n = t;
}
if(m % n)
{
return getcd(n,(m % n));
}
else
{
return n;
}
}
主要计算过程分为三个步骤：
1、对输入的两个自然数m > n取余数r，使得0
2、如果r为0，n即为所求结果，直接返回
3、r不为0，则赋值m=n,n=r从步骤1开始重新执行
两自然数的公因数的定义说明了计算结果产生的条件。如果步骤1中计算出的余数r = 0，则较小的数为公因数。如果r!=0则自然数m、n的关系可表示为：m = kn + r（其中k为自然数），等式可以证明能整除m的任何数必定能整除n和r；等式进一步可变形为：r = m - kn，说明同时整除m、n的任何数也必定能整除r。也就是说，能整除m、n的数的集合与整除n、r的数的集合相等。所以辗转相除的方法成立。
再发布一个循环实现欧几里德算法的版本。
int getcd2(int m,int n)
{
if (m return 0;
}
if(m
int t=m;
m=n;
n=t;
}
int cd = 1;
while(1){
int r = m % n;
if(0==r)
{
cd = n;
break;
}
else {
m=n;
n=r;
}
}
return cd;
}
以上内容就是小编介绍怎么使用欧几里德算法的方法，希望本文对大家学习欧几里德有所帮助，更多精彩内容就在爱站技术频道。
上一篇：怎么使用getdate()函数
下一篇：8皇后问题的解法
