五十九、如何求N个数的最大公约数和最小公倍数

@Author：Runsen

编程的本质来源于算法，而算法的本质来源于数学，编程只不过将数学题进行代码化。 ---- Runsen

上次介绍了短除法的因式分解，下面正式进入求解：两个及以上个数的最大公约数与最小公倍数

基本要求： 求N个数的最大公约数和最小公倍数。用C或C++或java或python语言实现程序解决问题。

比如：输入三个数，分别是12 14 18，最后程序输出最大公约数2和最小公倍数336。

12 14 16
2
336

  

 

  
1
  
2
  
3
 

此题是蓝桥杯的一题难度偏上的算法题，在之前使用的是短除法，但是短除法求解最大公约数和最小公倍数的公因数都存在一定的困难。

在此前，之前介绍过四种方法，分别是辗转相除法，更相减损术，暴力法和短除法。

个人推荐辗转相除法。辗转相除法是求最大公约数的一种最简单方法。它的具体做法是：用较大数除以较小数，再用出现的余数（第一余数）去除除数

文章来源: maoli.blog.csdn.net，作者：刘润森！，版权归原作者所有，如需转载，请联系作者。

原文链接：maoli.blog.csdn.net/article/details/110958828