python - 寻找数的最大质因数的有效方法

Question

我在我找到的一个网站(欧拉项目)上做这道题，有一道题涉及找到一个数的最大质因数。我的解决方案在大量失败时失败，所以我想知道如何简化这段代码？

""" Find the largest prime of a number """


def get_factors(number):
    factors = []
    for integer in range(1, number + 1):
        if number%integer == 0:
            factors.append(integer)
    return factors

def test_prime(number):
    prime = True
    for i in range(1, number + 1):
        if i!=1 and i!=2 and i!=number:
            if number%i == 0:
                prime = False
    return prime

def test_for_primes(lst):
    primes = []
    for i in lst:
        if test_prime(i):
            primes.append(i)
    return primes


################################################### program starts here
def find_largest_prime_factor(i):
    factors = get_factors(i)
    prime_factors = test_for_primes(factors)
    print prime_factors


print find_largest_prime_factor(22)

#this jams my computer
print find_largest_prime_factor(600851475143)

它在使用大数字时失败，我猜这就是问题的重点。 (计算机卡住，告诉我内存不足，并询问我要停止哪些程序)。

*************************************** 感谢您的回答.无论如何，代码中实际上存在一些错误。所以这个(低效代码)的固定版本如下。

""" Find the largest prime of a number """


def get_factors(number):
    factors = []
    for integer in xrange(1, number + 1):
        if number%integer == 0:
            factors.append(integer)
    return factors

def test_prime(number):
    prime = True
    if number == 1 or number == 2:
        return prime
    else:
        for i in xrange(2, number):
            if number%i == 0:
                prime = False
    return prime


def test_for_primes(lst):
    primes = []
    for i in lst:
        if test_prime(i):
            primes.append(i)
    return primes


################################################### program starts here
def find_largest_prime_factor(i):
    factors = get_factors(i)
    print factors
    prime_factors = test_for_primes(factors)
    return prime_factors


print find_largest_prime_factor(x)

Answer 1

根据您的方法，您首先在 O(n) 中生成数字 n 的所有除数，然后在另一个 O 中测试这些除数中的哪个是质数(n) test_prime 的调用次数(反正是指数级的)。

更好的方法是观察，一旦您找到一个数的除数，您就可以反复除以它以去除它的所有因数。因此，为了得到质因数，比如 830297，您测试所有小素数(缓存的)，并且对于每一个除以您的数字的素数，您继续除以:

• 830297 可以被 13 整除，所以现在您将使用 830297/13 = 63869
进行测试
• 63869 仍然可以被 13 整除，你在 4913
• 4913 不除以 13，下一个质数是 17 将 4913 除以得到 289
• 289 仍然是 17 的倍数，您有 17，它是除数和停止。

---

为了进一步提高速度，在测试下面缓存的质数后，比如 100，您必须使用 test_prime 函数(根据 @ 更新)测试质数除数Ben 的回答)但是反过来，从 sqrt 开始。您的数字可以被 71 整除，下一个数字的 sqrt 为 91992，这有点接近于 6857这是最大的质因数。