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