Project Euler 3 | 寒山烟雨
现在的位置: 首页 > 小试身手 > 正文

Project Euler 3

2012年06月25日 小试身手 ⁄ 共 853字 ⁄ 字号 评论 3 条 ⁄ 阅读 1,590 views 次

今天是第三题——

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.

0
【上篇】
【下篇】

目前有 3 条留言    访客:2 条, 博主:1 条

  1. tusooa 2012年06月28日 下午1:07  @回复  Δ-49楼 回复

    perl perl perl


    • 管理员
      hsyyf 2012年06月28日 下午9:22  @回复  ∇地下1层 回复

      不用perl,不想和ee样冥顽不化。。。

  2. Zhengheng Li 2012年06月25日 下午10:52  @回复  Δ-48楼 回复

    Max@FactorInteger[600851475143]
    结果正确 :lol:

给我留言

留言无头像?


×