今天是第三题——
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从大往小筛选的实现——
#========================================================================
# FileName: Project.py
# Author: hsyyf
# Email: 931107419@qq.com
# HomePage: http://www.hsyyf.me
# LastChange: 2012-06-25 13:23:04
#========================================================================
def fun(m):
k=int(math.sqrt(m))
for i in range(2,k):
if m%i==0:
return 0
return 1
import math
N=600851475143
m=int(math.sqrt(N))
for i in range(m,2,-1):
if N%i==0:
if fun(i):
break
print(i)
结果为6857.
perl perl perl
不用perl,不想和ee样冥顽不化。。。
Max@FactorInteger[600851475143]
结果正确 😆