基本概念
- 最小公倍数：两个或多个整数公有的倍数叫做它们的公倍数。整数a，b的最小公倍数记为[a，b]，同样的，a，b，c的最小公倍数记为[a，b，c]，多个整数的最小公倍数也有同样的记号。
- 最大公约数：也称最大公约数、最大公因子，指两个或多个整数共有约数中最大的一个。a，b的最大公约数记为（a，b），同样的，a，b，c的最大公约数记为（a，b，c），多个整数的最大公约数也有同样的记号。
- 关于最小公倍数与最大公约数，我们有这样的定理：(a,b)[a,b]=ab(a,b均为整数)。
方法分析
最大公约数
- 辗转相除法：
设两数为a、b(a≥b)，求a和b最大公约数的步骤如下：
① a%b得余数c
② 若c=0，则b即为两数的最大公约数
③ 若c≠0，则a=b，b=c，再回去执行① - 更相减损法：
设两数为a、b，求a和b最大公约数的步骤如下：
① 若a > b，则a=a-b。
② 若a < b，则b=b-a。
③ 若a = b，则a（或b）即为两数的最大公约数。
④ 若a ≠ b，则再回去执行①。
例如求27和15的最大公约数过程为：
27－15＝12( 15>12 ) 15－12＝3( 12>3 )
12－3＝9( 9>3 ) 9－3＝6( 6>3 )
6－3＝3( 3==3 )
因此，3即为最大公约数。
最小公倍数
- (a,b)[a,b]=ab
先算出ab及[a,b]相除即为最小公倍数。 - 穷举法：
设两数为a、b(a≥b)，t=a,i=1求a和b最小公倍数的步骤如下：
① a%b得余数c
② 若c=0，则a即为两数的最小公倍数
③ 若c≠0，则i=i+1,a=t*i，再回去执行①
代码实现
最大公约数
- 辗转相除法：
int HCD(int x, int y)
{
int temp;
if (x < y) //如果x<y交换x,y
{
temp = x;
x = y;
y = temp;
}
while (x%y) //x%y！=0时
{
temp = x;
x = y; //将y赋给x
y = temp % y; //余数赋给y
}
//直到x%y == 0时y为最大公约数
return y;
}- 更相减损法：
int HCD(int x, int y)
{
int MAX = x > y ? x : y;
int MIN = x < y ? x : y;
int TEMP = MAX - MIN;
if (TEMP == 0)
return MAX; //递归终止
else
HCD(TEMP, MIN);//递归
}最小公倍数
- (a,b)[a,b]=ab
//求最大公约数 辗转相除法
int HCD(int x, int y)
{
int temp;
if (x < y) //如果x<y交换x,y
{
temp = x;
x = y;
y = temp;
}
while (x%y) //x%y！=0时
{
temp = x;
x = y; //将y赋给x
y = temp % y; //余数赋给y
}
//直到x%y == 0时y为最大公约数
return y;
}
//求最小公倍数(a,b)[a,b]=ab
int ICM(int x, int y)
{
return x*y / HCD(x, y);
}- 穷举法：
//求最小公倍数
int ICM(int x, int y)
{
int temp;
int i = 1;
if (x < y) //如果x<y交换x,y
{
temp = x;
x = y;
y = temp;
}
temp = x;
while (x%y) //x%y！=0时
{
i++;
x = temp * i;//将x*1、x*2...赋给x
}
//直到x%y == 0时x为最小公倍数
return x;
}参考文章：
内容来源于网络如有侵权请私信删除
- 还没有人评论，欢迎说说您的想法！
客服
