python 中的质因数分解程序没有输出

Question

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

The prime factors of 13195 are 5, 7, 13 and 29.What is the largest prime factor of the number 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 上调用此函数时，我没有得到任何输出。此外，我也没有收到任何错误消息。运行一段时间，简单重启shell

我知道这不是一个优雅的代码，我猜我是通过暴力破解大量这样的问题导致了这个问题？究竟是怎么回事？

Answer 1

这是当我尝试使用 Python 2.7 运行你的代码时发生的情况：

$ python primes.py
Killed: 9

问题是 range(2, 600851475143) 试图创建一个包含 600851475141 个元素的列表。这太大了，无法容纳在您的计算机内存中，因此 Python 程序被终止。

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

P.S。您的代码中还有一个错误，这意味着它不适用于质数输入。

Answer 2

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

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 3

考虑到问题的规模，您编写的两个函数都有问题。 q_prime(a) 循环到 a 并且 prime_factor(x) 循环到 x 每次迭代调用 q_prime。这使得你的算法 O(N^2) 对于像 600851475143.

这样的数字来说太多了

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

生成器函数使用 sieve of Eratosthenes 产生素数
遍历素数直到 sqrt(n) 收集因子，同时缩小 n 每个找到的因子
- 如果没有找到其他因素，请添加 n 本身

python 中的质因数分解程序没有输出

Prime factorisation program in python gives no output

python

prime-factoring