首页 > 代码库 > 欧几里得求最大公约数
欧几里得求最大公约数
欧几里得算法（又称辗转相除法）
定理：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)。
code
/** * 求最大公约数 * * 欧几里德算法又称辗转相除法，用于计算两个整数a，b的最大公约数。 * 其计算原理依赖于下面的定理：gcd(a,b) = gcd(b,a mod b) * */ 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)); } }
我是天王盖地虎的分割线
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。