寒山烟雨

今天是第三题——

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 0
13
    return 1
14
 
15
import math
16
N=600851475143
17
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.