python - 我的 python 程序不会在终端中执行或显示任何内容

Question

所以我试图解决一个项目欧拉问题，要求我们找到 600851475143 的最大质因数。这是我的代码:

factors = [i for i in range(1,600851475144) if 600851475143%i is 0]
prime_factors = []
for num in factors:
    factors_of_num = [i for i in range(1, num+1) if num%i is 0]
    if factors_of_num == [1, num]:
        prime_factors.append(num)
print(max(prime_factors))

问题是此代码不会像这样对大量数据运行。\我怎样才能让它发挥作用？

Answer 1

你的程序正在执行，但是range(1, 600851475144)只是花了很长时间的 rrrrrrrrrrrrrrrrrrrrrrrrrrr有很多更好的方法来获取质因数，而不是先单独检查每个数字是否是除数，然后再检查其中哪些是质数。

首先，对于每对除数 p * q = n , p或 q必须是 <= sqrt(n) , 所以你实际上只需要检查 range(1, 775147) 中的数字获得这些对中的一部分并免费获得另一对。仅此一项就足以使您的程序及时完成。但是您仍然会得到所有的除数，然后必须检查其中哪些是素数。

接下来，您实际上不必获取这些除数的所有素因数来确定它们是否为素数:您可以使用any一旦找到第一个非原始因素就停止。在这里，也测试了 sqrt(num)足够。 (此外，您可以从最大的除数开始，这样您就可以在找到第一个质数后立即停止循环。)

---

或者，一旦找到一个除数，就将目标数除以该除数，直到不能再除为止，然后继续使用新的、更小的目标数和下一个可能的除数。这样，您的所有除数都保证是素数(否则数字已经被它的素数减少)，并且您还需要更少的测试(除非这个数字本身就是质数)。