欧几里得算法求最大公约数

Sometimes your whole life boils down to one insane move. 人这一辈子，有时就得靠一次疯狂的举动才能扭转乾坤。 ------------------《阿凡达》

文章目录

欧几里得算法求最大公约数一、介绍欧几里得二、实现思路三、核心思想四、优点五、核心代码

一、介绍欧几里得

---

  像所有博客一样，出于尊重，介绍一下这位伟大的数学家欧几里得。

  欧几里得，古希腊人，数学家，主要成就：数学巨著《几何原本》、欧几里得算法、完全数。

  在柏拉图学派晚期导师普罗克洛斯（约410～485）的《几何学发展概要》中，就记载着这样一则故事，说的是数学在欧几里得的推动下，逐渐成为人们生活中的一个时髦话题(这与当今社会截然相反)，以至于当时亚里山大国王托勒密一世也想赶这一时髦，学点儿几何学。

  虽然这位国王见多识广，但欧氏几何却令他学的很吃力。于是，他问欧几里得“学习几何学有没有什么捷径可走？”，欧几里得笑道：“抱歉，陛下!学习数学和学习一切科学一样，是没有什么捷径可走的。学习数学，人人都得独立思考，就像种庄稼一样，不耕耘是不会有收获的。在这一方面，国王和普通老百姓是一样的。” 从此,“在几何学里,没有专为国王铺设的大道。”这句话成为千古传诵的学习箴言。   总之呢，任何事情都是这样，哪有这么多得捷径可走，天才往往都是天天积累成才。

二、实现思路

---

定义2.1：设m和n是两个不全为0的整数，称m与n的公因子中最大的为m与n的最大公因子，或最大公约数(greatest common divisor)，记作gcd(m,n) 定义2.2：设m和n是两个非零整数，称a与b最小的公倍数为m与n的最小公倍数(least common multiple)，记作lcm(m,n)

---

欧几里得算法又称辗转相除法 s：设两个正整数m，n且m > n ; s1：令r=m%n（%代表取余）； s2：若r=0(即n整除m)运算结束，n为结果 ； s3：否则令m=n，n=r并返回s1 ；

三、核心思想

gcd(m,n)=gcd(n,mod(m,n) lcm(m,n) = ab/gcd(m,n)

证明：不妨设 m=k₁d ,n=k₂d , k₃ = m/n (整除) 则 r=m-k₃n=k₁d-k₂k₃d=(k₁- k₂k₃)d 故r也是d的倍数，得证$gcd(m,n)=gcd(n,mod(m,n)gcd(m,n)=gcd(n,mod(m,n)gcd(m,n)=gcd(n,mod(m,n)$gcd(m,n)=gcd(n,mod(m,n)

四、优点

一看相比于穷举法，效率也会高很多

五、核心代码

int gcd(int m,int n) { int t,r; if(m<n) swap(m,n); //交换二者的值 while(n!=0) { r=m%n; m=n; n=r; } return m; } int gcd(int m,int n) // 递归做法 { if(m<n) swap(m,n); //交换二者的值 if(n==0) return m; return gcd(n,m%n); } int lcm(int gcd,int m,int n) { return m/gcd*n; } 123456789101112131415161718192021222324

参考来源：人物简介源自百度百科

在上的第一篇文章，２０１９加油！