python中的质因式分解程序不提供输出

Question

我正在研究欧拉问题 3 的项目，

13195的质因数是5、7、13和29.数600851475143的最大素因数是多少？

我想出的代码如下：

def q_prime(a):
    if a == 2:
            return True
    elif a < 2:
            return False
    for i in range(2,a):

            if a%i == 0:
                    return False
    else:
            return True

def prime_factor(x):
    prime_factors =[]
    for i in range(1,x):
            if q_prime(i) == True and x%i == 0:
                    prime_factors.append(i)
    return prime_factors

调用这个函数 13195 给了我 [5,7,13,29]，如预期的那样。我尝试了一些其他组合，例如 1035，它给出了 [3,5,23]。但是，当我在600851475143上调用此函数时，我没有得到任何输出。此外，我也没有收到任何错误消息。它运行了一段时间，简单地重新启动外壳

我知道这不是一个优雅的代码，我猜暴力破解我的方式解决了大量的这样的问题，导致了这个问题？到底是怎么回事？

Answer 1

数字

600851475143太大。如果在 q_prime 和 prime_factor 中检查范围 [2， sqrt(n(+1] 中不在范围 [2， n] bun 中的数字，则可以简化计算。这也将返回正确的结果，但花费的时间更少：

import math
def q_prime(a):
    if a == 2:
            return True
    elif a < 2:
            return False
    for i in range(2, int(math.sqrt(a) + 1)):
            if a%i == 0:
                return False
    else:
        return True

def prime_factor(x):
    prime_factors =[]
    for i in range(1, int(math.sqrt(x) + 1)):
            if q_prime(i) == True and x%i == 0:
                    prime_factors.append(i)
    return prime_factors

Answer 2

考虑到问题的大小，您编写的两个函数都有问题。 q_prime(a)循环到a，prime_factor(x)循环到x调用q_prime每次迭代。这使得你的算法O(N^2)这对于像600851475143这样的数字来说太多了。

更好的方法(O(√N( ->基本上是立竿见影的结果(：

• 使用埃拉托色尼筛产生素数的生成器函数
• 循环遍历素数，直到sqrt(n)收集因子，同时缩小n找到的每个因子
  • 如果没有找到其他因素，请添加n本身

Answer 3

以下是我尝试使用 Python 2.7 运行您的代码时发生的情况：

$ python primes.py
Killed: 9

问题是range(2, 600851475143)尝试创建600851475141元素的列表。这太大了，无法容纳计算机的内存，因此Python程序被杀死了。

您可以尝试将range()替换为 xrange() ，但您的程序需要很长时间才能完成。你需要一个更好的算法。

附言您的代码中还有一个错误，这意味着它不适用于素数输入。