Project Euler 3解题报告

题目:The prime factors of 13195 are 5, 7, 13 and 29.


What is the largest prime factor of the number 600851475143 ?


题目3:找出一个合数的最大质数因子
13195的质数因子有5,7,13和29.


600851475143的最大质数因子是多少?


<a href="http://projecteuler.net/problem=3" target="_blank">Project Euler problem 3</a>


版本一:


先找出素数,然后确定最大的素因数。时间大概为37秒左右,属于很自然的但是效率很低的方法



import time, math
def findprimefactor(maxnum):
primefactor=[2,3,5,7]
i=9
while i flag=True
q=int(math.sqrt(i))
k=0
while(primefactor[k] p=primefactor[k]
if not(i%p):
flag=True
break
else:
flag=False
k+=1
if not flag:
primefactor.append(i)
i+=2
return primefactor


if __name__=='__main__':
strart=time.time()
L=findprimefactor(775147)
for num in L[::-1]:
if 600851475143%num==0:
print num
break
else:
print 600851475143
print time.time()-strart



版本二:


这个方法是利用除2外所有的素因数都是奇数的特点来完成,简单而且效率很高,时间为0.002秒



import time
strart=time.time()
d, n = 3, 600851475143
while (d * d &amp;lt; n):
if n % d == 0:
n /= d
else: d += 2
print n
print time.time()-strart