我的GCF / GCD程序返回了一个额外的数字

Question

我希望我的程序只返回最大的公因数，但它返回一堆随机因子，最后返回答案。

我尝试使用一个显示代码步骤的网站。

list_fac = []
def gcf(num1, num2):
x = max(num1, num2)
for i in range(2,x + 1):
if x % i == 0:
list_fac.append(i)

y = min(num1, num2)
for t in list_fac:
if y % t != 0:
list_fac.remove(t)
print(max(list_fac))

我希望它返回一个答案，但它返回一些因素，然后返回一个答案。

gcf(10,20)

预期：

10

实际：

2
10

Answer 1

这段代码基本上是正确的。如果不是 1，则在list_fac[-1]有答案。您可以通过从range(1, x + 1)迭代来解决此问题：

def gcf(num1, num2):
list_fac = []
x = max(num1, num2)
y = min(num1, num2)
for i in range(1, x + 1):
if x % i == 0:
list_fac.append(i)
for t in list_fac:
if y % t != 0:
list_fac.remove(t)
return list_fac[-1] if list_fac else 0
if __name__ == "__main__":
print(gcf(10, 20)) # => 10

但是，该代码效率低下且难以遵循。例如，内部循环不需要在list_fac上迭代两次(list.remove()遍历整个列表(。

您只需要考虑添加的最后一个元素是否也能被零整除。也没有必要将整个列表保存在内存中，因为我们只关心最后添加的内容(到目前为止最大的元素(：

def gcf(num1, num2):
greatest = 0
x = max(num1, num2)
y = min(num1, num2)
for i in range(1, x + 1):
if x % i == 0 and y % i == 0:
greatest = i
return greatest

我建议按如下方式使用欧几里得算法(有关为什么复杂性是线性改进的详细信息，请参阅链接的文章或此线程(：

def gcd(a, b):
while b:
a, b = b, a % b
return a

更简单的是，Python的人有一个内置的：

Python 3.7.2 (default, Mar 11 2019, 20:44:31)
[GCC 4.8.4] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> from math import gcd
>>> gcd(10, 20)
10

Python 3.4.3 (v3.4.3:9b73f1c3e601, Feb 24 2015, 22:43:06) [MSC v.1600 32 bit (Intel)] on win32
Type "help", "copyright", "credits" or "license" for more information.
>>> from fractions import gcd
>>> gcd(10, 20)
10

以下是验证例程的快速测试：

from random import randint
from math import gcd
def gcf(num1, num2):
list_fac = []
x = max(num1, num2)
y = min(num1, num2)
for i in range(1, x + 1):
if x % i == 0:
list_fac.append(i)
for t in list_fac:
if y % t != 0:
list_fac.remove(t)
return list_fac[-1] if list_fac else 0
if __name__ == "__main__":
passes = 0
tests = 10000
for i in range(tests):
a, b = randint(0, 100), randint(0, 100)
if gcd(a, b) == gcf(a, b):
passes += 1
print(f"{passes}/{tests} passed") # => 10000/10000 passed

快速基准测试：

gcd 0.7560891520042787
gcf 39.11557542099763
gcf improved 32.58505471699755

import timeit
from math import gcd
def gcf(num1, num2):
list_fac = []
x = max(num1, num2)
for i in range(2,x + 1):
if x % i == 0:
list_fac.append(i)
y = min(num1, num2)
for t in list_fac:
if y % t != 0:
list_fac.remove(t)
def gcf2(num1, num2):
greatest = 0
x = max(num1, num2)
y = min(num1, num2)
for i in range(1, x + 1):
if x % i == 0 and y % i == 0:
greatest = i
return greatest
def a(): gcd(20, 125)
def b(): gcf(20, 125)
def c(): gcf2(20, 125)
if __name__ == '__main__':    
print("gcd", timeit.timeit("a()", setup="from __main__ import a"))
print("gcf", timeit.timeit("b()", setup="from __main__ import b"))
print("gcf improved", timeit.timeit("c()", setup="from __main__ import c"))