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

最近开始做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