原题链接 http://projecteuler.net/problem=9

Special Pythagorean triplet

A Pythagorean triplet is a set of three natural numbers, a < b < c, for which,
a2 + b2 = c2
For example, 32 + 42 = 9 + 16 = 25 = 52.

There exists exactly one Pythagorean triplet for which a + b + c = 1000.
Find the product abc.

特殊的毕达哥拉斯三元组

一个毕达哥拉斯三元组指的是三个自然数, a < b < c ,且

a2 + b2 = c2

例如,32 + 42 = 9 + 16 = 25 = 52.

有且只有一组毕达哥拉斯三元组满足 a + b + c = 1000.

求abc的乘积

解答:

将 c = 1000 - a - b代入a2 + b2 = c2

得到1000 (a + b) = 500000 + a b

暴力找到满足这个条件的a和b.

原题链接 http://projecteuler.net/problem=8

Largest product in a series
Find the greatest product of five consecutive digits in the 1000-digit number.

73167176531330624919225119674426574742355349194934
96983520312774506326239578318016984801869478851843
85861560789112949495459501737958331952853208805511
12540698747158523863050715693290963295227443043557
66896648950445244523161731856403098711121722383113
62229893423380308135336276614282806444486645238749
30358907296290491560440772390713810515859307960866
70172427121883998797908792274921901699720888093776
65727333001053367881220235421809751254540594752243
52584907711670556013604839586446706324415722155397
53697817977846174064955149290862569321978468622482
83972241375657056057490261407972968652414535100474
82166370484403199890008895243450658541227588666881
16427171479924442928230863465674813919123162824586
17866458359124566529476545682848912883142607690042
24219022671055626321111109370544217506941658960408
07198403850962455444362981230987879927244284909188
84580156166097919133875499200524063689912560717606
05886116467109405077541002256983155200055935729725
71636269561882670428252483600823257530420752963450

连串数字的最大乘积
求这1000个数字中,连续5个数字的乘积的最大值

解答:
这题没什么好说的。

原题链接 http://projecteuler.net/problem=7

10001st prime

By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.

What is the 10 001st prime number?

第10001个素数

列出前六个素数:2, 3,5, 7, 11,和13,我们可以知道第6个素数是13.

求第10001个素数。

解答:
没有想到什么好的方法,就用暴力解决。经过观察,对于大于6的正整数都可以用6n,6n + 1,6n + 2,6n + 3,6n + 4,6n + 5表示,其中只有6n + 1,6n + 5有可能是素数。所以可以用一个step变量来记录下一跳的步数,保证需要判断的数字在6n + 1和6n + 5中变换。要判断一个正整数是否是素数,只需用比它的平方根小的所有素数去除它,如果它可以被其中一个整除,则是素数,否则不是。

原题链接 http://projecteuler.net/problem=6

Sum square difference

The sum of the squares of the first ten natural numbers is,
12 + 22 + … + 102 = 385
The square of the sum of the first ten natural numbers is,
(1 + 2 + … + 10)2 = 552 = 3025
Hence the difference between the sum of the squares of the first ten natural numbers and the square of the sum is 3025 - 385 = 2640.

Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.

和平方差

前10个自然数的平方和是,

12 + 22 + … + 102 = 385

前10个自然数的和的平方是,

(1 + 2 + … + 10)2 = 552 = 3025

因此前10个自然数的和的平方与平方的和之间的差是 3025 - 385 = 2640.

求前100个自然数的和的平方与平方的和之间的差。

解答:

其实就是用公式

(1^2 + 2 ^2 + \ldots + n^2 = \frac{1}{6}n(n + 1)(2n + 1))

((1 + 2 + \ldots + n)^2 = (\frac{1}{2}n(n+1))^2)

原题链接http://projecteuler.net/problem=5

Smallest multiple

2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.

What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?

最小乘积

2520是能够被1到10整除的正整数中最小的。

求能够被1到20整除的正整数中最小的。

解答:

其实这题就是求1到10中的素数出现的最多次数,例如1到10中有素数2,3,5,7。其中2出现的次数最多为3次,即8;3出现的次数最多为2次,即9;其它为1次.所以最终的结果是8 9 5 * 7,即2520.

对于1到20,则有素数2,3,5,7,11,13,17,19.其中2出现的次数最多为4次,即16;3出现的次数为2,即9;其它都为 1次。所以最终的结果是16 9 5 7 11 13 17 * 19。

原题链接http://projecteuler.net/problem=4
Largest palindrome product
A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 * 99.

Find the largest palindrome made from the product of two 3-digit numbers.

最大的回文乘积

回文数的定义是从左右两边读都是相同的。在两个两位数的乘积中,最大的回文数是9009 = 91 * 99.

求两个三位数的乘积中,最大的回文数是什么?

解法:
这题没找到什么好的方法,暴力解决。

原题链接http://projecteuler.net/problem=3

Largest prime factor
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的最大素数因子?

解法:
这一题本来想先求出600851475143的以内的素数,然后再从最小的素数开始,找到它的最大因子。可是程序运行时出现了OverflowError: Python int too large to convert to C long错误,也就是600851475143已经超出了C语言中整型的范围,这是因为xrange这个函数的范围限制在C的long长度,在32位的机器中,传入xrange的数不能大于2 ** 31 - 1.上网找这个错误时,在StackOverFlow中找到了这个错误的解答,其中有一个人给出了一个方法。
下面举例来说明这个方法,例如要求360的素数因子,先从素数2开始,360一直除以2知道不在整除,得到45;之后一直除以素数3知道不能整除,得到5;之后3 + 2得到5,于是除以5,得到1,结束。

原题地址 http://projecteuler.net/problem=2

Even Fibonacci numbers

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 exceed four million, find the sum of the even-valued terms.

偶数斐波纳契数
斐波那契数列中的每一个数等于前面两个数的和,从1和2开始,前面十项为:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89,。。。

考虑斐波那契数中不超过4000000的数,求这些数中所有偶数的和。

解法:

这题不多说,关键是生成斐波那契数列,这里使用了一个迭代器的技巧。代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#!/usr/bin/python
# -*- coding:utf-8 -*-
'''
Created on 2013-4-26

@author: shilong
@email: long470884130@163.com
'''


def fibonacci():
"""一个迭代函数,每次得到一个斐波那契数,依次将得到1, 2, 3, 5..."""
a = 1
b = 1
while True:
yield a
a, b = a + b, a

if __name__ == "__main__":
fi = fibonacci()
s = 0
while True:
n = next(fi)
if n >= 4000000:
break
if n % 2 == 0:
s += n
print s

决定以后有空时就翻译欧拉工程,从今天开始。不知道应不应该把解法贴出来,有点损人品了,还是决定贴吧。

原文链接 http://projecteuler.net/problem=1

Multiples of 3 and 5

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.

3和5的倍数

如果我们列出10以内是3或者5的倍数的自然数,我们将得到3,5,6和9.这些倍数的总和是23.

求1000以内3或者5的倍数的总和。

解答:

最直接的方法,判断[1, 1000)中的自然数,将是3或者5的倍数相加,Python就一句

1
print sum([i for i in xrange(1, n) if i % 3 == 0 or i % 5 == 0])

还有一种更简便的方法,可以直接用笔算出来。例如求[1, 1000)中3的倍数的和,
这里3的倍数是3,6,9,。。。,999。也就是3 1,3 2,3 3,。。。3 333。所以求得1 + 2 + 。。。+ 333后乘以3就得到了最终结果,写成Python代码如下。

1
sum(xrange(1, 1 + (1000 - 1) / 3)) * 3

昨天去找堂姐,看到堂姐买给她儿子的玩具,其中一个是放格子玩具。也就是在一个有6 6,一共36格的盒子中,放入6个1,6个2,6个3,。。。,6个6,使得各行各列的数字不重复。这个挺简单的,于是对它进行扩展,也就是在各行各列的数字不重复的基础上,还要求斜边不重复,当场没做出来,回来之后写程序。想起了以前的八皇后问题,运行了一下
N皇后问题解的个数
1 1
2 0
3 0
4 2
5 10
6 4
7 40
8 92
9 352
10 724
11 2680
12 14200
13 73712
14 365596
15 2279184
16 14772512
17 95815104
发现六皇后问题,只有4个解,所以断定上面的扩展问题无解。不知道上面的数字有什么规律。顺便做了以下两个问题。
问题1
在n
n个格子里填入 n 个1,n个2,。。。 n 个 n使得各行各列出现的数字不重复
如在3 3的格子中填入
1 2 3
3 1 2
2 3 1
这个就可以满足条件
问对于1
1, 2 2 ,3 3, …, 6 6分别有几种填法?
解答如下
1 1
2 2
3 12
4 576
5 161280
由于6
6 时解的个数已经很多,程序跑的很慢,所以这个次数还不知道。

问题2
在n n个格子里填入 n 个1,n个2,。。。 n 个 n使得各行各列,以及斜边出现的数字不重复
此时对于3
3的格子中填入
1 2 3
3 1 2
2 3 1
这个就不可以满足条件了,因为从左上角往右下角方向看,有3 3,1 1 1,2 2 在同一条直线上。
而对于 5 5的格子中填入
1 2 3 4 5
3 4 5 1 2
5 1 2 3 4
2 3 4 5 1
4 5 1 2 3
这个就可以满足条件了。
问对于1
1, 2 2 ,3 3, …, 6 * 6分别有几种填法?
解答如下
1 1
2 0
3 0
4 0
5 240
6 0