003. 最大质因数(largest prime factor)

13195的质因数分别为5,7,13与29,600851475143最大的质因数是多少?

分析:求解质因数的方法较多,最常用的方法为短除法,即对于任意大于2的自然数N,先用N除以2,再用所得之商即(N/2)再除以2,直到商不能为2所整除,此时将被除数加一并比较其平方是否小于被除数,如果小于则再用商除以3,如不能整除,则除以5(因为所有2的倍数即偶数因数已在第一轮不断除以2时被排除了,所以之后都要加二)。这样循环下去直到除数的平方不再小于被除数,则退出循环,最后得到的N即为最大的质因数。实际执行中,要分两层循环,外层循环判断除数的平方是否小于被除数,内层循环判断被除数是否可以整除除数。

def main(n=600851475143):
    i = 2
    while i * i < n:
        while n%i == 0:
            n /= i
        i += 2 if i>2 else 1
    return n