0

我在 python 中使用以下算法实现了一个 lcm 问题。我的代码如下：

# Uses python3
import sys

def gcd_efficient(a, b):
    #current_gcd = 1
    #for d in range(2, min(a, b) + 1):
    #   if a % d == 0 and b % d == 0:
    #        if d > current_gcd:
    #            current_gcd = d

    #return current_gcd

    remainder = max(a, b) % min(a, b)
    newMax = min(a, b)
    if remainder == 0:
        return newMax

    return  gcd_efficient(newMax, remainder)


def lcm_efficient(a, b):
    #for l in range(1, a*b + 1):
    #   if l % a == 0 and l % b == 0:
    #        return l

    product = a*b
    gcd = gcd_efficient(a, b)
    lcm = product/gcd
    return int(lcm)

print(lcm_efficient(226553150, 1023473145))

现在我已经使用上面的代码来计算作为输入的大整数的 lcm。

但是我发现对于一些大整数：例如，当输入是： 输入：226553150 1023473145 python 控制台的输出是：46374212988031352 但实际输出应该是：46374212988031350

实际输出与给定输出仅相差 2。但是，令我困惑的是，为什么 python 解释器在执行上述代码时会在输出中给出错误。

这个错误可以取消吗？

等待答案！！

4

1 回答 1

1

你的问题在这里：

lcm = product/gcd

它应该是

lcm = product//gcd

以保证整数除法。您对 C++ 的翻译假定该/运算符在 C++ 和 Python 中的工作方式相同。在 Python 2 中确实如此。但在 Python 3 中不是。在 Python 3 中，/需要浮点除法，因此原始版本要求将两个操作数都转换为浮点数（在此过程中会丢失精度），然后再进行浮点除法。您的return语句将浮点结果转换回int，从而掩盖了问题。

于 2018-01-14T12:36:07.343 回答