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

2017-12-21 19:48:14来源:cnblogs.com作者:子非寒人点击

分享
第七城市

基本概念

  1. 最小公倍数:两个或多个整数公有的倍数叫做它们的公倍数。整数a,b的最小公倍数记为[a,b],同样的,a,b,c的最小公倍数记为[a,b,c],多个整数的最小公倍数也有同样的记号。
  2. 最大公约数:也称最大公约数、最大公因子,指两个或多个整数共有约数中最大的一个。a,b的最大公约数记为(a,b),同样的,a,b,c的最大公约数记为(a,b,c),多个整数的最大公约数也有同样的记号。
  3. 关于最小公倍数与最大公约数,我们有这样的定理:(a,b)[a,b]=ab(a,b均为整数)。

方法分析

最大公约数

  1. 辗转相除法:
    设两数为a、b(a≥b),求a和b最大公约数的步骤如下:
    ① a%b得余数c
    ② 若c=0,则b即为两数的最大公约数
    ③ 若c≠0,则a=b,b=c,再回去执行①
  2. 更相减损法:
    设两数为a、b,求a和b最大公约数的步骤如下:
    ① 若a>b,则a=a-b
    ② 若a

最小公倍数

  1. (a,b)[a,b]=ab
    先算出ab及[a,b]相除即为最小公倍数。
  2. 穷举法:
    设两数为a、b(a≥b),t=a,i=1求a和b最小公倍数的步骤如下:
    ① a%b得余数c
    ② 若c=0,则a即为两数的最小公倍数
    ③ 若c≠0,则i=i+1,a=t*i,再回去执行①

代码实现

最大公约数

  1. 辗转相除法:
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赋给xy = temp % y;   //余数赋给y}//直到x%y == 0时y为最大公约数return y;}
  1. 更相减损法:
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); //递归}

最小公倍数

  1. (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赋给xy = temp % y;   //余数赋给y}//直到x%y == 0时y为最大公约数return y;}//求最小公倍数(a,b)[a,b]=abint ICM2(int x, int y){return x*y / HCD2(x, y);}
  1. 穷举法:
//求最小公倍数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;}

参考文章:

  1. 常见算法:C语言求最小公倍数和最大公约数三种算法——CSDN
  2. C语言计算2个数的最小公倍数——博客园
  3. 百度百科
第七城市

最新文章

123

最新摄影

闪念基因

微信扫一扫

第七城市微信公众平台