[关闭]
@songpfei 2016-05-14T07:19:16.000000Z 字数 1032 阅读 1008

最大公约数和最小公倍数

OJ_算法


1. 基本概念

最小公倍数:数论中的一种概念,两个整数公有的倍数成为他们的公倍数,其中一个最小的公倍数是他们的最小公倍数,同样地,若干个整数公有的倍数中最小的正整数称为它们的最小公倍数,维基百科:定义点击打开链接

求最小公倍数算法:

最小公倍数=两整数的乘积÷最大公约数

2.求最大公约数算法:

2.1 辗转相除法

有两整数a和b:

① a%b得余数c

② 若c=0,则b即为两数的最大公约数

③ 若c≠0,则a=b,b=c,再回去执行①

  1. int GreatestCommonDivisor(int a,int b)//辗转相除法求两数的最大公约数
  2. {
  3. int temp;
  4. if (a < b)
  5. {
  6. temp = b;
  7. b = a;
  8. a = temp;
  9. }
  10. while (b!=0)
  11. {
  12. temp = a%b;
  13. a = b;
  14. b = temp;
  15. }
  16. return a;
  17. }
  1. int LeastCommonMultiple (int a,int b) /*自定义函数求两数的最小公倍数*/
  2. {
  3. int temp;
  4. temp=GreatestCommonDivisor(a,b); /*调用自定义函数,求出最大公约数*/
  5. return (a*b/temp); /*返回最小公倍数到主调函数处进行输出*/
  6. }

2.2 相减法

有两整数a和b:

① 若a>b,则a=a-b

② 若a

③ 若a=b,则a(或b)即为两数的最大公约数

④ 若a≠b,则再回去执行①

  1. int GreatestCommonDivisor(int a,int b)//相减法求两数的最大公约数
  2. {
  3. while (a!=b)
  4. {
  5. if (a > b)
  6. a = a - b;
  7. else
  8. b = b - a;
  9. }
  10. return a;
  11. }

2.3 穷举法

有两整数a和b:

① i=1

② 若a,b能同时被i整除,则t=i

③ i++

④ 若 i <= a(或b),则再回去执行②

⑤ 若 i > a(或b),则t即为最大公约数,结束

改进:

① i= a(或b)

② 若a,b能同时被i整除,则i即为最大公约数,

结束

③ i--,再回去执行②

有两整数a和b:

① i=1

② 若a,b能同时被i整除,则t=i

③ i++

④ 若 i <= a(或b),则再回去执行②

⑤ 若 i > a(或b),则t即为最大公约数,结束

改进:

① i= a(或b)

② 若a,b能同时被i整除,则i即为最大公约数,

结束

③ i--,再回去执行②

3.参考:

  1. http://blog.csdn.net/iwm_next/article/details/7450424
  2. http://blog.csdn.net/cyg0810/article/details/7980402
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注