时间戳

首页 > 解决方案 > 我的 GCF/GCD 程序返回一个额外的号码

python - 我的 GCF/GCD 程序返回一个额外的号码

问题描述

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

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

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

标签： pythonpython-3.xmath

解决方案

这段代码基本上是正确的。list_fac[-1]如果不是 1，您的答案是 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"))

推荐阅读