首页 > 代码库 > 【170723】一个简洁的求最大公约数算法
【170723】一个简洁的求最大公约数算法
1 import java.util.Scanner; 2 3 public class ZuiDaGongYueShuClass { 4 5 public static void main(String[] args) { 6 Scanner in = new Scanner(System.in); 7 int a = in.nextInt(); 8 int b = in.nextInt(); 9 while (b != 0) { 10 int r = a % b; 11 a = b; 12 b = r; 13 } 14 System.out.println(a); 15 in.close(); 16 } 17 }
//代码来自MOOC中国 翁恺 零基础学习Java
此处的核心算法在于:
1 while (b != 0) { 2 int r = a % b; 3 a = b; 4 b = r; 5 }
在此例中,原本的a、b中分别存放用户输入的两个整数,经过此循环的计算,a中将存放最终结果即最大公约数。
证明方法如下:(来自百度百科)
证法一
a可以表示成a = kb + r(a,b,k,r皆为正整数,且r<b),则r = a mod b
假设d是a,b的一个公约数,记作d|a,d|b,即a和b都可以被d整除。
而r = a - kb,两边同时除以d,r/d=a/d-kb/d=m,由等式右边可知m为整数,因此d|r
因此d也是b,a mod b的公约数
假设d是b,a mod b的公约数, 则d|b,d|(a-k*b),k是一个整数,
进而d|a.因此d也是a,b的公约数
因此(a,b)和(b,a mod b)的公约数是一样的,其最大公约数也必然相等,得证。
证法二
第一步:令c=gcd(a,b),则设a=mc,b=nc
第二步:可知r =a-kb=mc-knc=(m-kn)c
第三步:根据第二步结果可知c也是r的因数
第四步:可以断定m-kn与n互素【否则,可设m-kn=xd,n=yd,(d>1),则m=kn+xd=kyd+xd=(ky+x)d,则a=mc=(ky+x)dc,b=nc=ycd,故a与b最大公约数≥cd,而非c,与前面结论矛盾】
从而可知gcd(b,r)=c,继而gcd(a,b)=gcd(b,r),得证
【170723】一个简洁的求最大公约数算法
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。