C语言——求最大公约数及最小公倍数

基本概念

最小公倍数：两个或多个整数公有的倍数叫做它们的公倍数。整数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]=abint 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;}

参考文章：

常见算法：C语言求最小公倍数和最大公约数三种算法——CSDNC语言计算2个数的最小公倍数——博客园百度百科

呼唤你前往另一个地方，过上另一种生活。