首页 > 代码库 > 多种方法求最大公约数+求最小公倍数
多种方法求最大公约数+求最小公倍数
本文将给出求两个数a和b的最大公约数的几种可行方法。
方法一：辗转相除法
算法分析：有两个数a和b,用辗转相除法。
不妨设a>b,
首先求a和b的余数，b赋值给a，余数赋值给b；
重复以上操作，直到余数为0；
b值即为两数的最大公约数。
代码：
1 int zdgys(int a,int b) 2 { 3 int temp; 4 if( a<0 ) a=-a; 5 if( b<0 ) b=-b; 6 if( a<b ) { temp=a;a=b;b=temp; } // 让a>b 7 if( b==0 ) return a; 8 9 while( a%b!=0 ) //辗转相除10 { 11 temp=a%b;12 a=b;13 b=temp;14 }15 return b; //最大公约数为b16 }
方法二：
算法分析：两个数a和b的公约数与a-b和b的公约数是相同的，最大公约数也是相同的。
例如：函数 int func(int a,int b) 是求a和b的最大公约数，参数a和b，返回值为要求的最大公约数。
根据以上的分析，func(42,30) = func(30,12) = func(18,12) = func(12,6) = func(6,6) = func(6,0) =6.
求得的6即为42和30的最大公约数。
代码：
1 int gcd(int a,int b)2 {3 if( a<b )4 return gcd(b,a); //保证a始终大于b(a>b)5 if( 0==b ) //递归函数的终止条件6 return a;7 else8 return gcd(a-b,b);9 }
方法三：
算法分析：1.若X=2*X1,Y=2*Y1，则F(X,Y)=2*F(X>>1,Y>>1);
2.若X=2*X1,Y!=2*Y1，则F(X,Y)=2*F(X>>1,Y);
3.若X!=2*X1,Y=2*Y1，则F(X,Y)=2*F(X,Y>>1);
4.若X!=2*X1,Y!=2*Y1，则F(X,Y)=2*F(Y,X-Y)。
代码：
1 int gcd(int a,int b) 2 { 3 if( a<b ) 4 return gcd(b,a); 5 if( 0==b ) 6 return a; 7 else 8 { 9 if( IsEvent(a) ) //IsEvent(a) 满足a=2*a1(a1=a>>1)10 {11 if( IsEvent(b) )12 return ( gcd(a>>1,b>>1) <<1 ); // → 2*gcd(a/2,b/2)13 else 14 return gcd(a>>1,b); //→ gcd(a/2,b)15 }16 else 17 {18 if( IsEvent(b) )19 return gcd(a,b>>1); //→ gcd(a,b/2)20 else 21 return gcd(b,a-b); //→ gcd(b,a-b)22 }23 }24 }
附加：求两个数a和b的最小公倍数
分析：a和b的最小公倍数等于这两个数的乘积除以这两个数的最大公倍数。
代码：
1 int zxgbs(int a,int b)2 {3 if( 0==b ) return a;4 if( 0==a ) return b;5 return (a*b)/zdgys(a,b); //zdgys(a,b)→求a和b 的最大公约数6 }
多种方法求最大公约数+求最小公倍数
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。