擅长:python、mysql、java
<p>虽然您所实现的确实是一个GCD查找器,但它不是Euclid的算法</p>
<p>这就是你所做的:</p>
<pre><code>if the two numbers are equal
return either one as the GCD
else
return the GCD of the absolute difference between them and the smaller number
</code></pre>
<p>你的算法通过重复减法找到GCD。虽然这并没有错,但它肯定不是欧拉的算法(虽然它很接近)。在</p>
<p>欧拉算法可以:</p>
^{pr2}$
<p>因为欧几里德的算法使用模运算符,所以它所需的步骤要少得多,而事实上,计算的步骤与算法相同。因此,它的效率更高。在</p>
<p>以下是欧几里得算法的实现:</p>
<pre><code>def GCDfinder(a,b):
while b != 0:
a,b = b, a%b
return a
>>> GCDfinder(12,20)
4
>>> GCDfinder(17,20)
1
>>> GCDfinder(3,4)
1
</code></pre>