zhtlancer's blog

好久没有动这个了，今天再扫一道水题。

Find the largest prime factor of a composite number.
The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143 ?

题目的数据规模很小，所以可以直接偷懒穷举，so…

#!/usr/bin/env python  

num = 600851475143
seg_size = 10000
base_factor = 0
prime_factors = []

while base_factor*seg_size < num:
    for tmp in range(seg_size*base_factor, seg_size*(base_factor+1)):
        if tmp>1 and num%tmp == 0:
            prime_factors.append(tmp)
            while num%tmp == 0:
                num = num / tmp
            print "num:",num," ",tmp
        base_factor = base_factor + 1

print prime_factors