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

最近开始做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]))
  • http://zym8903.wordpress.com gazelle

    it is kind of fun of the Project, a little bit like the PKU-ACM.

  • whenov

    1. “在函数里,先将N里的2除完,余下的商M是0或者一个奇数。”打错了吧
    2. python里现成的max()怎么不用呢?
    3. A clearer implementation:
    def largest_prime_factor(n):
    while n % 2 == 0:
    n /= 2
    if n == 1:
    return 2

    factor = 3
    while True:
    while n % factor == 0:
    n /= factor
    if n == 1:
    return factor
    factor += 2

  • whenov

    没缩进。。。重发一个
    def largest_prime_factor(n):
    &ngsp;&ngsp;&ngsp;&ngsp;while n % 2 == 0:
    &ngsp;&ngsp;&ngsp;&ngsp;&ngsp;&ngsp;&ngsp;&ngsp;n /= 2
    &ngsp;&ngsp;&ngsp;&ngsp;if n == 1:
    &ngsp;&ngsp;&ngsp;&ngsp;&ngsp;&ngsp;&ngsp;&ngsp;return 2

    &ngsp;&ngsp;&ngsp;&ngsp;factor = 3
    &ngsp;&ngsp;&ngsp;&ngsp;while True:
    &ngsp;&ngsp;&ngsp;&ngsp;&ngsp;&ngsp;&ngsp;&ngsp;while n % factor == 0:
    &ngsp;&ngsp;&ngsp;&ngsp;&ngsp;&ngsp;&ngsp;&ngsp;&ngsp;&ngsp;&ngsp;&ngsp;n /= factor
    &ngsp;&ngsp;&ngsp;&ngsp;&ngsp;&ngsp;&ngsp;&ngsp;if n == 1:
    &ngsp;&ngsp;&ngsp;&ngsp;&ngsp;&ngsp;&ngsp;&ngsp;&ngsp;&ngsp;&ngsp;&ngsp;return factor
    &ngsp;&ngsp;&ngsp;&ngsp;&ngsp;&ngsp;&ngsp;&ngsp;factor += 2