【摘要】正式叙述前还写了一点自己的小感受。
问题：求两个正整数a，b的最大公约数。
大神看来是很简单的问题，但是对于去年夏天刚学python的我来说，这是个很难的问题，还记得当时一晚上睡不着都在想怎么快一点的求出最大公约数，后来猜测最小公倍数的求法，还有最后想出来的欣喜若狂，我现在还记忆犹新。

还记得看过一个小梗：一个农民种着种着地，一排一排的种，突然陷入深思，沉思良久，…

正式叙述前还写了一点自己的小感受。

问题：求两个正整数a，b的最大公约数。

大神看来是很简单的问题，但是对于去年夏天刚学python的我来说，这是个很难的问题，还记得当时一晚上睡不着都在想怎么快一点的求出最大公约数，后来猜测最小公倍数的求法，还有最后想出来的欣喜若狂，我现在还记忆犹新。

还记得看过一个小梗：一个农民种着种着地，一排一排的种，突然陷入深思，沉思良久，回去算了很久以后，借了钱疯了似的坐火车跑到中科院门口，等来数学系教授，向他讲述了自己的重大发现。大概意思就是，自己从田地中大彻大悟，发明了一种快速计算方法，不用计数，不用加法，不用数学，还给了教授一张伟大的定律表。

教授告诉他：你真的很厉害，你的发现很伟大，能在种田中悟出来这种算法可不容易。

但是，你发明的这种算法叫乘法，你给我的表，完善一下以后，叫九九乘法表。

农民继续回去种田

（这个故事告诉我们要多虚心接受知识，不要老自己想。。。。）

我知道了欧几里得算法以后，感觉自己就跟这个农民一样。。。。。。。

不过，知道了自己的想法就是欧几里得算法时，还是挺高兴的。。。

就当锻炼思维了吧。。只能这么安慰自己。

好，开始正题。。。。：：

我当时的思路是这样的：求a，b的最大公约数，假设最大公约数是x的话，a一定可以用i*x来表示，b也一定可以用j*x来表示，我们怎么把i和j去掉，把x榨出来呢？？

让这俩数不断互相相减就可以啦！

后来自己想到了互相取余。

我们来看正规的欧几里得算法：

首先放简介：欧几里德算法又称辗转相除法，是指用于计算两个正整数a，b的最大公约数。应用领域有数学和计算机两个方面。计算公式gcd(a,b) = gcd(b,a mod b)。

看代码实现：

Python



      def gcd(a, b):

      while a != 0:

       a, b = b % a, a

      return b

  

                    
        
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
软件开发