0

我必须编写一个代码来找到输入数字 10 ^ num 的两个最高互质因子。

现在，我已经写了：

def coprimes(num):
    for x in range (2, num):
        for y in range (2, num):
            while (gcd(x,y) == 1) & (x != y):
                if (x*y==num):
                    return (x,y)

由于forloops，这显然是一个非常慢的程序。每当我将它输入终端时，产生答案的速度太慢了。我也不确定这是否正确。你对我如何改进这种方法有什么建议吗？

此方法的示例答案应该是：

>>> coprimes(10)
(9765625, 1024)
4

1 回答 1

2

你要

return 2**num, 5**num

请注意，这个问题定义不明确——不清楚是否2**num, 5**num应该考虑高于1, 10**num. 然而，这对因素比任何其他因素都高。

要得出这个答案，请注意最多有 1 个因子可以被 2 整除，并且最多有 1 个因子可以被 5 整除。如果一个因子可以同时被 2 和 5 整除，则另一个必须为 1，并且任何整数都与 1 互质。如果一个因子可以被 2 整除，另一个可以被 5 整除，我们会选择 2 和 5 的最大幂。（2 或 5 不能除以两个数字的选项会产生较低的因子。）

于 2013-09-29T21:08:30.430 回答