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

Largest product in a grid

In the 20 * 20 grid below, four numbers along a diagonal line have been marked in red.

08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08
49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00
81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65
52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91
22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80
24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50
32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70
67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21
24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72
21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95
78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92
16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57
86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58
19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40
04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66
88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69
04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36
20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16
20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54
01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48

The product of these numbers is 26 63 78 * 14 = 1788696.

What is the greatest product of four adjacent numbers in the same direction (up, down, left, right, or diagonally) in the 20 * 20 grid?

在格子中最大的乘积

在下面的20 * 20的格子中,四个沿着对角线的数用红色标出

它们的乘积是 26 63 78 * 14 = 1788696.

求在这个20 * 20的格子中,四个相邻数的最大乘积(这四个相邻数必须在同一条直线上,向上,下,左,右,或者对角线)

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

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

Summation of primes

The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.

Find the sum of all the primes below two million.

素数的和

10以下的所有素数的和是 2 + 3 + 5 + 7 = 17.

求2000000以下所有素数的和。

解答:
用筛法求得2000000以下的所有素数,之后求和

写成代码如下:

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
#!/usr/bin/python
# -*- coding:utf-8 -*-
'''
Created on 2013-5-5

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

from math import sqrt
def generate_prime(n):
'''得到[1,n]以内的素数'''
primes = [True for i in xrange(n + 1)]
primes[0] = primes[1] = False
for i in xrange(2,int(sqrt(n)) + 1):
if primes[i]:
s = i ** 2
while s <= n:
primes[s] = False
s += i
primes = [i for i in xrange(2,n + 1) if primes[i]]
return primes

if __name__ == "__main__":
n = 2000000
primes = generate_prime(n)
print sum(primes)

原题链接 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