问题:快速求取正整数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 即可。
分享到:
相关推荐
课程的随堂作业,C语言的,用dev就能运行,萌新代码,勿喷,仅仅帮助不想写作业的朋友方便一下,反正老师也不会仔细检查的
用扩展欧几里得算法求任意两个数字的最大公因数
用欧几里得算法求最大公约数的c++代码,很完整,可以运行
欧几里得减法求最大公约数,欧几里得减法求最大公约数
java语言实现的欧几里得算法,求最大公约数,以及满足(a,b)=x*a+y*b的x和y
分解质因数,连续整除,欧几里得三种算法求最大公约数
欧几里得算法最大公约数1
这个是用递归法来写最大公约数,当然原算法还是欧几里得算法;只不过代码比较简洁
欧几里得算法连续整数检测法分解质因数法求最大公约数
通过欧几里得算法求到最大公约数,然后得出最小公倍数
JAVA实现求最大公约数和最小公倍数 根据欧几里得定律,最大公约数的递归算法
算法 1.连续整数检测 1. t = min {m , n}; 2. m 除以t , 如果余数为 0 , 则执行步骤 3 , 否则,执行第 4 步; 3. n 除以 t , 如果余数为 0 ,返回t 的值... 4....算法 2.欧几里得算法 1 .... 2 .... 3 .... 算法 3.分解质因数
实现求两个整数的最大公约数和最小公倍数。求两个数的最大公约数和最小公倍数的方法有很多种,常用的有欧几里得算法和Stein算法。
欧几里得 最大公约欧几里得 最大公约欧几里得 最大公约欧几里得 最大公约欧几里得 最大公约欧几里得 最大公约欧几里得 最大公约
本程序的设计目标为计算两数的最大公约数,采用的方法为辗转相除法,又名欧几里得算法采用辗转相除法计算任意两数的最大公约数
最大公约数问题的三种实现方法:欧几里得算法(辗转相除法)、试探法、因式分解法,不是完整的课程设计。
python怎么求最大公约数和最小公倍数 一、求最大公约数 用辗转相除法求最大公约数的算法如下: 两个正整数a和b(a>b),它们的最大公约数等于a除以b的余数c和b之间的最大公约数。比如10和25,25除以10商2余5,那么10...
求两个自然数m和n的最大公约数。 理解这样一个观点:不同的算法能够解决相同的问题,这些算法的解题思路不同,复杂程度不同,解题效率也不同。
求解最大公约数和最小公倍数的方法有很多种,如质因数分解法、短除法、辗转相除法(欧几里得算法)等。 在实际应用中,这两个概念广泛应用于数学各个分支以及日常生活中,如分数化简、时间与速度问题、工程设计等...
求两个自然数m和n的最大公约数。 分别使用三种算法实现: //连续整除算法 //欧几里得算法 //分解质因数算法 适用人群:算法入门或对算法很感兴趣的朋友,算是对算法有个初步的认识。 使用场景:本资源使用案例是...