「辗转相除法」又叫做「欧几里得算法」,是公元前 300 年左右的希腊数学家欧几里得在他的著作《几何原本》提出的.利用这个方法,可以较快地求出两个自然数的最大公因数,即 HCF 或叫做 gcd.
最大公约数(greatest common divisor,简写为gcd;或highest common factor,简写为hcf)
所谓最大公因数,是指几个数的共有的因数之中最大的一个,例如 8 和 12 的最大公因数是 4,记作 gcd(8,12)=4.
在介绍这个方法之前,先说明整除性的一些特点,注以下文的所有数都是正整数,以后不再重覆.
我们可以这样给出整除以的定义:
对於两个自然数 a 和 b,若存在正整数 q,使得 a=bq,则 b 能整除 a,记作 b | a,我们叫 b 是 a 的因数,而 a 是 b 的倍数.
那麼如果 c | a,而且 c | b,则 c 是 a 和 b 的公因数.
由此,我们可以得出以下一些推论:
推论一:如果 a | b,若 k 是整数,则 a | kb.因为由 a | b 可知 ha=b,所以 (hk)a=kb,即 a | kb.
推论二:如果 a | b 以及 a | c,则 a | (b±c).因为由 a | b 以及 a | c,可知 ha=b,ka=c,二式相加,得 (h+k)a=b+c,即 a | (b+c).同样把二式相减可得 a | (b-c).
推论三:如果 a | b 以及 b | a,则 a=b.因为由 a | b 以及 b | a,可知 ha=b,a=kb,因此 a=k(ha),hk=1,由於 h 和 k 都是正整数,故 h=k=1,因此 a=b.
辗转相除法是用来计算两个数的最大公因数,在数值很大时尤其有用而且应用在电脑程式上也十分简单.其理论如下:
如果 q 和 r 是 m 除以 n 的商及余数,即 m=nq+r,则 gcd(m,n)=gcd(n,r).
证明是这样的:
设 a=gcd(m,n),b=gcd(n,r)
则有 a | m 及 a | n,因此 a | (m-nq)(这是由推论一及推论二得出的),即 a | r 及 a | n,所以 a | b
又 b | r 及 b | n,所以 b | (nq+r),即 b | m 及 b | n,所以b | a.因为 a | b 并且 b | a,所以 a=b,即 gcd(m,n)=gcd(n,r).
例如计算 gcd(546, 429),由於 546=1(429)+117,429=3(117)+78,117=1(78)+39,78=2(39),因此
gcd(546, 429)
=gcd(429, 117)
=gcd(117, 78)
=gcd(78, 39)
=39
Java实现代码如下:
package com;
public class GcdTest
{
//循环实现
int gcd1(int a, int b)
{
int k = 0;
do
{
//得到余数
k = a % b;
//根据辗转相除法,把被除数赋给除数
a = b;
//余数赋给被除数
b = k;
} while (k != 0);
//返回被除数
return a;
}
//逆归实现
int gcd2(int a,int b)
{
//直到满足此条件逆归退出
if(b == 0)
{
return a;
}
if(a < 0)
{
return gcd2(-a,b);
}
if(b < 0)
{
return gcd2(a,-b);
}
return gcd2(b,a % b);
}
public static void main(String[] args)
{
GcdTest gt = new GcdTest();
System.out.println(gt.gcd1(888,458));
System.out.println(gt.gcd2(888, 458));
}
}
分享到:
相关推荐
辗转相除法证明辗转相除法证明辗转相除法证明辗转相除法证明
简单讲解用辗转相除法计算乘法逆元,用于密码学加密,附C语言实现算法(对正整数运算)
利用辗转相除法求两个数的最大公约数。要求能接受用户的输入,输出最大公约数。 辗转相除法原理: 已知a,b,c为正整数,若a除以b余c,则(a,b)=(b,c),其中用(a,b)来表示a和b的最大公约数。(证明过程请参考其它...
m = 9147485 n = 5147480 辗转相除法求最大公约数 最大公约数=?
实现多项式辗转相除法,多项式的系数精确至小数点后两位,具有良好的交互界面。
C语言程序设计-用辗转相除法求两个整数的最大公约数;.c
一个小小的exe文件,其中是我在学习网络安全数学期间编写的欧几里得除法/辗转相除法计算器。 也就是根据两个互素的整数a和b,通过辗转相除法算出两个整数s,t,使得sa+tb=1。
从几何的角度描述了辗转相除法的基本原理,非常值得借鉴
C#中辗转相除法的多种实现方式,内有完整源码.rar
c++编写的辗转相除法代码,可输入数字进行辗转相除运算(具有详细步骤),便于对辗转相除运算问题进行验证求解。
很古老的数学问题,文件里包含完整的工程文件..其实很简单,问题主要表现在算法里,希望对各位有用...
问题:求A关于模N的逆元B,即要找出整数B,使A×B mod N=1(或A×B=x×N+1),这里要求A和N互素。...方法:辗转相除法(即欧几里德算法) 该算法原用于求两个数的最大公约数,经过变形可用于求模逆元
辗转相除法,求最大公约数和最小公倍数。(网上收集的,自己学习用)。Ubuntu10.04+GCC4.4.3
欧几里德辗转相除法求最大公约数的C++实现 嗯,很经典、很简单的一个算法,是很多算法书的开篇第一个算法
辗转相除法计算两个整形参数的最大公约数。VC6.0编译通过。
C语言求最大公约数
辗转相除法求最大公约 辗转相除法 辗转相除法:辗转相除法是求两个自然数的最大公约数的一种方法,也叫欧几里德算法。 例如,求(319,377): ∵ 319÷377=0(余319) ∴(319,377)=(377,319); ∵ 377÷319=1...