高效寻找一个数的最大素因子的方法

Question

我在一个网站上做题（项目Euler），有个问题是要找出一个数字的最大质因数。我的解决方案在处理非常大的数字时失败了，所以我想知道怎么才能让这段代码更高效一些。

""" 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

试除法进行质因数分解的关键在于，分解一个数字时，最有效的办法并不需要先测试质数。

你只需要按顺序列出可能的因数，然后不断用这些因数去除目标数字——这样找到的因数一定是质数。当当前因数的平方超过要分解的数字时，就可以停止了。具体的代码可以参考user448810的回答。

通常情况下，试除法在处理质数时比处理所有数字（或者奇数等）要快，但如果只是分解一个数字，先找出质数再去测试除以它们，可能 可能会比直接用逐渐增大的可能因数要慢。这种列举的复杂度是O(n)，而生成质数的复杂度是O(n log log n)，使用的是埃拉托斯特尼筛法，其中n = sqrt(N)，N是上限。使用试除法（TD）时，复杂度是O(n^1.5/(log n)²)。

当然，这些复杂度只是个参考，实际代码中的常数因素可能会影响结果。例如，来自这里和这里的Haskell代码在分解600851475149（一个质数）时的执行时间：

2..                       0.57 sec
2,3,5,...                 0.28 sec
2,3,5,7,11,13,17,19,...   0.21 sec
primes, segmented TD      0.65 sec    first try
                          0.05 sec    subsequent runs (primes are memoized)
primes, list-based SoE    0.44 sec    first try
                          0.05 sec    subsequent runs (primes are memoized)
primes, array-based SoE   0.15 sec    first try
                          0.06 sec    subsequent runs (primes are memoized)

所以这要看情况。当然，分解复合数600851475143几乎是瞬间完成的，所以在这种情况下就无所谓了。

Answer 2

简单的质数测试可以通过几种方法来改进：

1. 先检查这个数能不能被2整除，然后从3开始循环，每次加2，这样只检查奇数。
2. 循环的结束条件设为这个数的平方根的上限值。因为超过这个值就不可能找到质因数了。
3. 提前用筛法生成一些质数，只有在这些质数用完后再用简单的方法去测试。

除了这些简单的改进，你还需要查找更高效的因数分解算法。

Answer 3

我的解决方案是用C#写的。我敢打赌你可以把它翻译成Python。我已经用从1到1,000,000,000的随机长整数字进行测试，效果很好。你可以试着用网上的质数计算器来验证结果。祝你编码愉快 :)

public static long biggestPrimeFactor(long num) {
    for (int div = 2; div < num; div++) {
        if (num % div == 0) {
            num \= div
            div--;
        }
    }
    return num;
}

Answer 4

这是我最喜欢的简单因式分解程序，使用的是Python语言：

def factors(n):
    wheel = [1,2,2,4,2,4,2,4,6,2,6]
    w, f, fs = 0, 2, []
    while f*f <= n:
        while n % f == 0:
            fs.append(f)
            n /= f
        f, w = f + wheel[w], w+1
        if w == 11: w = 3
    if n > 1: fs.append(n)
    return fs

这个程序的基本算法是试除法，它使用一种叫做“素数轮”的方法来生成试探性的因子。虽然它的速度没有直接用素数进行试除法快，但它的好处在于不需要计算或存储素数，所以使用起来非常方便。

如果你对用素数编程感兴趣，可以看看我博客上的这篇文章。

Answer 5

从你的方法来看，你首先是用 O(n) 的时间生成一个数字 n 的所有因数，然后又用 O(n) 的时间去测试这些因数中哪些是质数（这本身就是个比较复杂的过程）。

一个更好的方法是，发现一个数字的因数后，可以不断地用这个因数去除掉它的所有倍数。比如说，要找 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（最大的质因数）比较近。