Project Euler

网上有一个著名的”具有挑战性的不仅仅需要具备数学能力的‘数学/计算机编程’问题集合”–Project Euler ，他的网站是http://projecteuler.net，这个网站我在之前的 blog中也曾提到过。今天，我要将我目前为止做出的几道题目列出来：
Project Euler是个很有意思的地方，你可以使用任何方法解决上面的问题，你甚至可以直接通过搜索引擎获得答案，不过，那样就没意思啦。

第一题

英文原文如下：

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.
Find the sum of all the multiples of 3 or 5 below 1000.

中文译文：

列出10以下所有3或5的倍数，我们将得到3，5，6和9。他们的和是23。
求1000以下所有3或5的倍数之和。

下面是我写的 python程序的解法，不过并非最好的算法，他的时间复杂度为O(n)。

  1 #!/usr/bin/env python
  2 # -*- encoding: utf-8 -*-
  3 
  4 def find(dat):
  5     sum = 0
  6     for i in range(3,dat):
  7         if i % 3 == 0 or i % 5 == 0 :
  8             sum = sum + i
  9     return sum
 10 
 11 if __name__ == "__main__":
 12     print(find(1000))

网上还有更简短的python的解法：

 print(sum(i for i in range(1000) if i%3 == 0 or i%5 == 0))

根据容斥原理改进算法：

$sum(n) = \sum\limits_{i=1}^{\lfloor\frac{n}{3}\rfloor}3i + \sum\limits_{i=1}^{\lfloor\frac{n}{5}\rfloor}5i-\sum\limits_{i=1}^{\lfloor\frac{n}{15}\rfloor}15i$
$\sum\limits_{i=1}^n ki = k\frac{(n)(n+1)}{2}$

 def sumltoN(n):
    return n * (n+1) /2
 def sumMultiples(limit, a):
    return sumltoN((limit -1) /a) * a
 sumMultiples(1000, 3) + sumMultiples(1000, 5) - sumMultiples(1000,15)

这个算法的时间复杂度是O(1)的。

当你解答完一道题目之后，你可以进入到论坛的讨论区，看看别人是怎么解决这道问题的，我第一次进去的时候，第一眼看到的就是一个人用8086的汇编程序解决了这道问题，当时惊了我一下，呵呵。

第二题

英文原文：

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:
    1,2,3,5,8,13,21,34,55,89,...
By considering the terms in the Fibonacci sequence whose values do not excedd four million, find the sum of the even-valued terms.

中文译文：

斐波那契数列中的每一项，都是由前两项相加而得。如果从1和2开始，则前面10个元素将会是：
    1,2,3,5,8,14,21,34,55,89,...
求出斐波那契数列最大值不超过四百万的所有偶数元素的和。

我的解法如下：

 1 #!/usr/bin/env python
 2 # -*- encoding: utf-8 -*-
 3 
 4 sum = 2
 5 a = 1
 6 b = 2
 7 c = a+b
 8 while c < 4000000 :
 9     if c % 2 == 0:
10         sum = sum + c
11     a,b = b,c
12     c = a+b
13 
14 print(sum)

可以看出这个解法的算法复杂度还是O(n)的。

第三题

英文原文：

The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143?

中文译文：

13195的质因数是 5，7，13和29。
那么600851475143的最大的质因数是什么？

这个问题实际就是一个分解质因数的问题，怎么去分解呢？我们知道质数是除了1和自己本身没有其他因数的数，下面有一个求解100以内质数的程序：

#!/usr/bin/env python

print 2
for i in range(100):
    for j in range(2,i):
        if i % j == 0:
            break
        if j > (i/2):
            print i
            break

有种想法就是先生成一个质数表，然后用这个表里的数一个一个的去除那个数，我们手工分解质因数就经常使用这样的方法，我在后来的讨论中也发现了有人使用Ruby解决这道问题的时候就用到了一个质数生成器。
不过这样做还是有点麻烦，要现生成一堆质数，而且还不一定用的上。还好网上搜索发现，已经有前人发现了一个很好的算法。1975年，John M. Pollard提出了一种新的算法，算法时间复杂度为 $O(n^{\frac{1}{4}})$ .示例代码如下：

program rho;
var
n,i:longint;
begin
 readln(n); {输入需要分解的数}
 write(n,'=1');
 i := 2;
 while i<= n do
     begin
        while n mod i = 0 do
            begin
                write('*',i);
                n := n div i;
            end;
         inc(i);
     end;
end.

需要注意的是，使用Pascal或者是C这种静态编译语言，在处理600851475143这么大的数字时，即使是使用长整型也会溢出。所以需要修改以上程序，使他支持更长的类型。不过Python就没有这个问题了，以下是用Python改写的上述代码，python会在发现溢出的时候自动转换成范围更大的数据类型。

#!/usr/bin/env python
# -*- encoding: utf-8 -*-

num = 600851475143
div = 2
while div <= num:
    while num \% div ==0:
        print '*\%d'\% div
        num = num / div
    div = div +1

在我的Archlinux中，我还发现了一个小程序 factor，直接使用这个小东西，他就可以直接计算出一个数字的所有质因数。

$ factor 600851475143
600851475143: 71 839 1471 6857

###参考资料

百度百科分解质因数
维基百科欧拉计划

上一篇：最近做的小项目

下一篇： qmake 项目文件的写法

本站采用知识共享署名-非商业性使用-相同方式共享3.0 中国大陆许可协议进行许可,转载请注明出处。

推荐使用 chrome 浏览器浏览本站。

Hu Zhenyu's Blog

about

Project Euler

第一题

第二题

第三题