用Python解答 ProjectEuler问题(3)

E003
The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?

求600851475143的最大质因子。

今天重写了求素数的方法

# -*- coding:utf-8 -*-

class Prime:
    primes = [2]

    def __init__(self, maxpri):
        self.expandList(maxpri)

    def testNumber(self, x):
        """
        根据已知素数表用筛法进行测试x
        """
        assert type(1)==type(x) #x必须是整数
        if x<2:
            return False
        isPri = True
        for p in self.primes:
            if p*p>x: #只需测试被sqrt(x)以内的素数整除
                break
            elif 0==x%p: #是合数
                isPri = False
                break
        return isPri

    def expandList(self, maxpri, length=None):
        """
        扩展素数表到接近maxpri，或个数达到length
        """
        x = self.primes[-1]
        while (True):
            x += 1
            if self.testNumber(x):
                # Python中改写类成员需要用self.__class__.引用
                self.__class__.primes.append(x)
            #是否达到目标并退出
            if maxpri and x>=maxpri:
                break
            if length and len(self.primes)>=length:
                break


if __name__ == '__main__':
    max = 100    
    pri = Prime(max*max)
    print str(pri.primes)

有了上面求素数的代码，现在我们可以这样解决问题

from prime import Prime
from math import sqrt, floor

def problem3(number):
    lmt = floor(sqrt(number))
    factor = 0
    pri = Prime(lmt)
    for p in pri.primes:
        if 0==number%p:
            factor = p
    return factor

if __name__ == '__main__':
    print str(problem3(600851475143))