算法一
任何>1的整数都可以写成一个或多个素数因子乘积的形式,且素数乘积因子以非递减序出现。
则整数x,y可以分别标记为:
x=p1p2...pm
y=p1p2...pm
(其中p1,p2,....是素数,若有必要素数因子的指数xj或yj可以为0)
(1)最大公约数 gcd(x,y)=p1p2...pm
(2)最小公倍数 lcm(x,y)=p1p2...pm
(3)因此,亦可得:lcm(x,y)*gcd(x,y)=x*y
按如上思路计算gcd(x,y)至少需要如下两步
step1: decompose_to_primes(int n);//把整数n分解成素数相乘的形式
step2:get_gcd(int x,int y);//根据step1的结果按照公式(1)计算gcd(x,y)
分明显计算量比较大。
实际上从编程的角度来看,在x,y的数值不是很大的情况下。若是单纯的计算最大公约数和最小公倍数可以不必这么复杂,可以从大到小遍历min(x,y)的约数,找到的第一个公约数即为所求。
int get_gcd(int x,int y)
{
int temp;
int i;
if(x>y)
{
temp=x;
x=y;
y=temp;
}
if(y%x==)
return x;
for(i=x/;i>;i--)
if(x%i==)
if(y%i==)
return i;
return ;
} int get_lcm(int x,int y)
{
return (x*y)/(get_gcd(x,y));
}
算法二
用Euclid算法(即辗转相除法)
step1、令r为a/b所得余数(0≤r<b)。若 r= 0,算法结束,则b 即为所求,否则执行step2。
step2、a←b,b←r,重新执行step1。
int gcd(int x,int y)//Euclid method
{
int r;
if(x<y)
{
r=x;
x=y;
y=r;
}
r=x%y;
while(r)
{
x=y;
y=r;
r=x%y;
}
return y;
}