在数学界,辗转相除法,又称欧几里得算法,被认为是世界上最早的算法(公元前300年),该算法用于求两个最大公约数的算法。辗转相除法首次出现于欧几里得的《几何原本》(第VII卷,命题yⅠ和Ⅱ)中,而在中国则可以追溯至东汉出现的《九章算术》。
两个自然数的最大公约数是能够同时整除它们的最大的正整数。辗转相除法基于如下原理:两个整数的最大公约数等于其中较小的数和两数的相除余数的最大公约 数。例如,1254和390的最大公约数是6(1254 = 6 × 209;390 = 6 × 65);用这两个数推导最大公约数的过程如下:
1254 % 390 = 84
390 % 84 = 54
84 % 54 = 30
54 % 30 = 24
30 % 24 = 6
所以这两个数的最大公约数是6,这很明显是递归算法
这个算法的证明如下:
设两数为a、b(b<a),用gcd(a,b)表示a,b的最大公约数,r=a mod b 为a除以b以后的余数,k为a除以b的商。辗转相除法即是要证明gcd(a,b)=gcd(b,r)。
第一步:令c=gcd(a,b),则设a=mc,b=nc
第二步:根据前提可知r =a-kb=mc-knc=(m-kn)c
第三步:根据第二步结果可知c也是r的因数
第四步:可以断定m-kn与n互素【否则,可设m-kn=xd,n=yd,(d>1),则m=kn+xd=kyd+xd=(ky+x)d,则a=mc=(ky+x)dc,b=nc=ycd,故a与b最大公约数成为cd,而非c,与前面结论矛盾】
从而可知gcd(b,r)=c,继而gcd(a,b)=gcd(b,r)。
PS:这个结论是根据第二步r =(m-kn)c,第一步b =nc 将r带入gcd(b,r),得到gcd(nc, (m-kn)c),所以只有n和m-kn互为素数,b和r的最大公约数才为c
下面给出Java的实现
public class Euclideanalgorithm
{
public static int getGCD(int a, int b)
{
if(a < 0 || b < 0)
return -1;
if(a < b)
{
int c = b;
b = a;
a = c;
}
int c = a % b;
if(c == 0)
return b;
else
return getGCD(b, c);
}
public static void main(String[] args)
{
System.out.println(getGCD(1254, 390));
}
}
分享到:
相关推荐
辗转相除法:辗转相除法是求两个自然数的最大公约数的一种方法,也叫欧几里德算法。 例如,求(319,377): ∵ 319÷377=0(余319) ∴(319,377)=(377,319); ∵ 377÷319=1(余58) ∴(377,319)=(319,...
辗转相除法求最大公约数,这是一种很古老得算法,也很有用高效,有利于大家学习
辗转相除法求两个数的最大公约数算法
欧几里德辗转相除法求最大公约数的C++实现 嗯,很经典、很简单的一个算法,是很多算法书的开篇第一个算法
辗转相除法,又称欧几里得算法,是一种古老的用于计算两个正整数最大公约数(Greatest Common Divisor, GCD)的方法。该方法基于一个数学原理:对于任意两个正整数a和b(a>b),它们的最大公约数等于a除以b的余数c和b...
问题:求A关于模N的逆元B,即要找出整数B,使A×B mod N=1(或A×B=x×N+1),这里要求A和N互素。 方法:辗转相除法(即欧几里德算法) 该算法原用于求两个数的最大公约数,经过变形可用于求模逆元
简单讲解用辗转相除法计算乘法逆元,用于密码学加密,附C语言实现算法(对正整数运算)
辗转相除法求最大公约 辗转相除法,也称为欧几里得算法,是求解两个整数的最大公约数的一种有效方法。
递归求n 个数最大公约数和用辗转相除法求最大公约数
求两个数最大公约数,利用欧几里德算法,辗转相除法。详细内容看资料,留作备份。
用辗转相除法求两个数的最大公约数的步骤如下: 先用小的一个数除大的一个数,得第一个余数; 再用第一个余数除小的一个数,得第二个余数; 又用第二个余数除第一个余数,得第三个余数; 这样逐次用后一个...
python求最大公约数和最小公倍数 #辗转相除法 def gcd(a,b): #最大公约数函数,且最小公倍数 = 两个数相乘 / 最大公约数 if b == 0: return a else: return gcd(b,a%b) print("请输入两个数:") j,k = input()....
包含两个算法,一个为辗转相除法,一个为连续整数检测法。而且算法中加入计数法对比两种算法的时间复杂度。
VB 求多个数的最大公约数,这应该是个比较... r = m Mod n '辗转相除法求最大公约数 If r = 0 Then Exit Do '找到最大公约数后即退出 m = n n = r Loop big = n '返回这两个数的最大公约数 End Function
辗转相除法,求最大公约数及最小公倍数. 供算法初学者使用.
主要介绍了Python基于递归和非递归算法求两个数最大公约数、最小公倍数,涉及Python递归算法、流程循环控制进行数值运算相关操作技巧,需要的朋友可以参考下
很古老的数学问题,文件里包含完整的工程文件..其实很简单,问题主要表现在算法里,希望对各位有用...
之前总结过一次高德纳TAOCP中的最大公约数求解,其实课后题中的算法修改要求实现的是辗转相除法求解最大公约数。 这个题目我最初的理解理解错了,自然也没有做出标准答案。现在按照标准答案的解答写一下相应的代码...
ACM常用的算法:辗转相除法求最大公约数
此程序可以实现对两个整数求最大公约数,所用得法为递归算法。