欢迎手机类测试同行交流,可加群 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

 

评分:0

我来说两句

显示全部

:loveliness: :handshake :victory: :funk: :time: :kiss: :call: :hug: :lol :'( :Q :L ;P :$ :P :o :@ :D :( :)

我的栏目

日历

« 2020-04-01  
   1234
567891011
12131415161718
19202122232425
2627282930  

数据统计

  • 访问量: 10033
  • 日志数: 14
  • 建立时间: 2013-08-06
  • 更新时间: 2014-06-30

RSS订阅

Open Toolbar