欢迎手机类测试同行交流,可加群 19591195,加群时请注明来源于51testing,谢谢。
【Project Eular - Python】Problem 3: Largest prime factor
上一篇 /
下一篇 2013-08-14 11:07:55
最近一直在看些
python的东西,属于刚起步的哪一种;然后就找到了欧拉,就当是一遍
学习一边练手了吧。下面是其中的第三个问题,刚开始的时候用range(xrange等)函数,然后判断,结果发现python脚本执行了20多个小时,一半都还没有计算完成,因此就开始琢磨怎么去优化了,感兴趣的朋友可以看下。
下面就是题目:
The prime factors of 13195 are 5, 7, 13 and 29.What is the largest prime factor of the number 600851475143 ?
题目给出了一个12位数的数字,然后要求得到其最大的质因数。至于质因数是什么,这个是数学的范畴,这里也就不去赘述了。
【一】原始脚本
最早的想法就是从2开始,一直到目标数,对出现的每个数字先做判断其是否为目标是的质因数,如果是,放到一个数组里,最后取数组中的最大值即可,代码如下:
def compute_prime(number):
for i in range(2, number):
if number % i == 0:
return False
break
执行脚本的时候才发现,计算量实在是太大了,一个小时才计算了9位数级别,照这样下去,目测整整运行3,4天都一定能得到结果,这个离我们要求的12位数级差太多了,因此有了下面的第二版优化。
【二】初级优化
由于取的值只最大值,所以就想到了从目标数开始,往下递减,代码如下:
a = []
def count_prime(number):
for i in range(number - 1, 1, -1):
if number % i == 0:
a.append(i)
return a
def main():
List = count_prime(600851475143)
print(List)
for j in range(len(List)):
if compute_prime(List[j]):
print(List[j])
break
执行脚本,虽然比上面有所提高,但仍然满足不了我们的要求,因此想到了下面的方法,也就是终极版的优化.
【三】最后的优化版
后来考虑到这个每个数都能通过质因数相乘得到,因此在实际运算中,我们把目标数除以较小的质因数,这样目标数就会进一步被分解,这样的话,我们就能避免很多不必要的运算量了。举例来说,我们要计算1000的最大质因数,第一步我们会发现2是其中的一个,那么目标数就从1000变成了500,这样相对于上面的两种算法,我们至少节省了一半的时间了;然后递归计算,直到我们得到最大的质因数。算法如下:
a = []
def prime(number):
i = 2
while number > 1:
if number % i == 0:
a.append(i)
number = number / i
else:
i += 1
return max(a)
print(prime(600851475143))
在windows eclipse和Ubuntu环境下,实测,得到目标数600851475143的最大质因数为6857;而最神奇的是,得到这个数仅仅需要不到1秒钟。
至此,问题三成功解决,上传答案,正确。
收藏
举报
TAG:
Python
python
Eular