今天是第三题——

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.

作者 hsyyf

《Project Euler 3》有3条评论

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注