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

Question

所以我试图解决一个项目 Euler 问题，该问题要求我们找到 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))

问题是这段代码不会像这样大量运行。\我怎样才能让它工作？

标签： python

Answer 1

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

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

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

---

或者，一旦你找到一个除数，将目标数除以该除数，直到它不能再被除，然后继续使用新的、更小的目标数和下一个潜在除数。这样，你的所有除数都保证是素数（否则这个数字已经被它的素数减少了），你也需要更少的测试（除非数字本身是素数）。