今天是第三题——
The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143 ?
今天这道题非常有意思,就是求600851475143的最大质因数。题目很简单作为一道编程题可以说是非常基础,只要有最基本的编程思想都能很快的解出来。然而,这道题略有陷阱的是这个数长度过大,对于32位的C,普通的INT和LONG没有办法处理。这时想到最简单的处理方法是用python,不受位数的限制。
其次,这道题的另一处陷阱是如何最快的找出最大质因数。乍一看这个数很大,开平方之后是7万多,第一想法是从大往小了筛选。但是算出来之后发现,其实这个结果并不大,从2开始筛选反而方便。
第一次算的时候没有注意第二个问题,python的计算量并不小,不过计算速度还是出乎意料,很快就出结果了。看来python的效率还是有潜力的。
python从大往小筛选的实现——
Python |copy code |?
01 #========================================================================
02 # FileName: Project.py
03 # Author: hsyyf
04 # Email: 931107419@qq.com
05 # HomePage: http://www.hsyyf.me
06 # LastChange: 2012-06-25 13:23:04
07 #========================================================================
08 def fun(m):09 k=int(math.sqrt(m))10 for i in range(2,k):11 if m%i==0:12 return 013 return 114 15 import math16 N=60085147514317 m=int(math.sqrt(N))18 for i in range(m,2,-1):19 if N%i==0:20 if fun(i):21 break
22 23 print(i)24
结果为6857.
0
管理员 hsyyf: 2012年06月28日 下午9:22 ∇地下1层