算出一个自然数的最大质因数

最近开始做Project Euler里的题目，做到第三题就有点小小的卡住了。第三题的题目如文章标题，需要找到一个自然数的最大质因数。

假设输入的自然数是N，最直接的方法是从小到大算出N的每一个因数，然后再判断这个因数是不是质数。显然这种算法的复杂度很高。在最坏情况下是O(N^2)的复杂度。

自己想更好的算法，没有想出来，只好借助于Google，看到了这样一个思路：

函数biggest(N)是求最大质因数的函数。

在函数里，先将N里的2除完，余下的商M是0或者一个奇数。如果是0，那么N是2的次方，2就是N的最大质因数。

如果余下的商是奇数，那么将M用从3开始的到sqrt(M)+1的奇数J试商。如果能被奇数J除尽，那么J一定是质数。再递归求M/J的商的最大质因数I，并将I与J比较，取较大的一个。

这个算法的巧妙之处就是用3开始的奇数试商。比如如果M能被3除尽，那么将3和biggest(M/3)比较。这样的递归，可以保证把M中的3都除尽，这样以来，3的次方就不会出现在返回结果里。同理，5、7、11这些质数也会被除尽。因此只要在试奇数商的时候被除尽了，那么这个奇数就是质数。

算法实现如下：

import sys
from math import sqrt

def find_largest_primef(n):
    is_prime = True
    if n == 2:
        return n
    if n%2 == 0:
        print n, 'getting rid of 2s..'
        is_prime = False
        return find_largest_primef(n/2)
    else:
        for i in range(3,int(sqrt(n))+1,2):
            print 'try ..', i
            if n%i == 0:
                print 'n: ', n, 'i: ', i
                is_prime = False
                return pick_larger(i, find_largest_primef(n/i))
    if is_prime:
        print n, 'is prime!'
        return n

def pick_larger(first, second):
    if first >= second:
        return first
    else: return second

if __name__ == '__main__':
    print find_largest_primef(int(sys.argv[1]))