我的编程学习日志(12)--求最大公约数,最小公倍数

分类: Uncategorized , C/C++ , algorithm

2014-09-24

|

622

|

评论:0

分享:

求最大公约数最基本的方法就是,用一个数每次加1,除这两个数。

最小公倍数就是两个数除以最大公约数的商相乘,再乘以最大公约数(a/gcd*b/gcd*gcd

化简以后就是a*b/gcd,

但在编程中,a*b很可能会超出范围,所以我们要先除再乘,即:a/gcd*b

 

代码:

int a=1,b=2,i=1,gcd,lcm;

for(;i<=(a<b?a:b);i++)

if(a%i==0&&b%i==0

gcd=i;

lcm= a/gcd*b;


 

 

最大公约数还有一种做法就是辗转相除法,

先用两个数中大的除以小的求余数,

c=a%b;

如果c不为0,

a=b;b=c;

继续c=a%b

直到c=0,最大公约数就是此时的b

 

我们可以用递归快速的完成这个过程

代码:

int gcd(int a,int b)

{return !b?a:gcd(b,a%b);}


 

 



标签:
本文共 0 个回复

发表评论 (对文章评论)

captcha