用Python解答 ProjectEuler问题(3)

ispsh

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))