问题:快速求取正整数a,b的最大公约数?
欧几里得算法(又称辗转相除法)
定理:gcd(a,b) = gcd(a,a mod b)
证明:对于任何正整数a,b。如果a>b,都有a=k*b+r 即r=a-k*b => r=a mod b.
假设d为a,b的公约数,则a=a1*d,b=b1*d。
而r=a1*d-k*b1*d=(a1-k*b1)*d => d也是r的约数 => d也是(a,r)的公约数
则说明(a,b)的公约数也就是(a,r)的公约数。因此gcd(a,b)=gcd(a,a mod b)。
/**
* 求最大公约数
*
* 欧几里德算法又称辗转相除法,用于计算两个整数a,b的最大公约数。
* 其计算原理依赖于下面的定理:gcd(a,b) = gcd(b,a mod b)
*
* @author heartraid
*/
public class EuclidDivisor {
public static int getDivisor(int a,int b){
if(a%b==0) return b;
if(b%a==0) return a;
return a>=b?getDivisor(a,a%b):getDivisor(a,b%a);
}
public static void main(String[] args) {
System.out.println(EuclidDivisor.getDivisor(12,8));
}
}
引申:
快速求取正整数a,b的最小公倍数?
首先求出a,b的最大公约数c=(a,b),然后用a*b/c 即可。
分享到:
相关推荐
欧几里得算法,也称为辗转相除法,是计算两个正整数最大公约数(Greatest Common Divisor, GCD)的一种经典方法。该算法基于以下原理:两个正整数a和b(a>b)的最大公约数等于a除以b的余数c和b之间的最大公约数。...
扩展欧几里得算法(Extended Euclidean Algorithm)不仅求出最大公因数,还能同时得到两个数的贝祖等式解,即存在整数x和y使得ax + by = gcd(a, b)。这对于计算模逆、线性同余方程的解等问题非常有用。 扩展...
用欧几里得算法求最大公约数的c++代码,很完整,可以运行
欧几里得减法求最大公约数,欧几里得减法求最大公约数
java语言实现的欧几里得算法,求最大公约数,以及满足(a,b)=x*a+y*b的x和y
本文将深入探讨三种不同的方法来计算两个整数的最大公约数:分解质因数法、连续整除法以及欧几里得算法,并结合提供的代码文件进行解析。 1. **分解质因数法**: 分解质因数法是通过将两个数分别分解为质因数,...
欧几里得算法最大公约数1 欧几里得算法是一种常用的算法,用来计算两个整数之间的最大公约数(Greatest Common Divisor,GCD)。该算法的时间复杂度为 O(log n),是一种高效的算法。 在上述代码中,我们可以看到,...
欧几里得算法是解决此类问题的有效方法,而通过最大公约数计算最小公倍数则是利用了数学中的基本公式。这些代码段可以帮助读者更好地理解如何在实际编程中应用这些概念。无论是学习数据结构与算法还是进行实际项目...
根据给定的信息,我们可以提取并总结出以下与“用辗转相除法求最大公约数”相关的知识点: ### 1. 辗转相除法(欧几里得算法)原理 辗转相除法是一种用于计算两个正整数最大公约数(Greatest Common Divisor, GCD...
求解最大公约数有多种方法,其中包括欧几里得算法,也被称为辗转相除法。这个算法基于这样一个原理:对于任何两个正整数a和b(假设a>b),它们的最大公约数等于a除以b的余数c和b之间的最大公约数。如果余数为0,则b...
这个是用递归法来写最大公约数,当然原算法还是欧几里得算法;只不过代码比较简洁
本主题主要关注求最大公约数(Greatest Common Divisor, GCD)和最小公倍数(Least Common Multiple, LCM)的三种常见算法,通过流程图的方式进行阐述。下面我们将详细探讨这五种算法及其流程。 1. 辗转相除法...
标题“例3-16求最大公约数.zip”暗示了一个编程示例,旨在实现计算两个或更多整数之间最大公约数(Greatest Common Divisor, GCD)的功能。这个压缩包可能包含一个C++项目或者任何其他编程语言的源代码,如Python、...
' 使用欧几里得算法求最大公约数 Do While a <> b If a > b Then a = a - b ElseIf b > a Then b = b - a End If Loop sdm_1 = a End Function ``` 在这个函数中,我们首先声明了两个变量`a`和`b`作为...
在编程领域,求最大公约数(Greatest Common Divisor, GCD)是一个常见的数学问题,尤其是在使用整数处理的场景中。C#作为.NET框架下的主要编程语言,提供了多种方式来实现这一功能。本篇文章将深入探讨如何用C#通过...
在求解最大公约数的问题上,VC++可以通过标准模板库(Standard Template Library, STL)中的算法或者自定义函数实现。 最大公约数是数学中一个基本概念,用于确定两个或多个整数的最大公共因数。在编程中,我们可以...
根据提供的文件信息,我们可以归纳出三个主要的知识点:利用连续整数检测法分解质因数求最大公约数、使用欧几里得算法求最大公约数以及字符串匹配算法(包括BF、KMP和BM算法)。接下来将对这些知识点进行详细的解释...
通过欧几里得算法求到最大公约数,然后得出最小公倍数
JAVA实现求最大公约数和最小公倍数 根据欧几里得定律,最大公约数的递归算法
欧几里得算法是求最大公约数最古老的算法,由古希腊数学家欧几里得提出。该算法基于以下定理:对于任意两个正整数a和b(a>b),它们的最大公约数等于a除以b的余数c与b之间的最大公约数。通过不断迭代这一过程,直到...