欧拉计划Python解法（第6题-第10题）

欧拉计划提供了几百道由易到难的数学问题，你可以用任何办法去解决它，当然主要还得靠编程，但编程语言不限，已经有Java、C#、Python、Lisp、Haskell等各种解法。

“欧拉计划”的官网是：https://projecteuler.net，你可以在这个网站上注册一个账号，当你提交了正确答案后，可以在里面的论坛里进行讨论，借鉴别人的思路和代码。

如果你的英文不过关，有人已经将几乎所有的题目翻译成了中文，网址：http://pe-cn.github.io。

强烈建议你在看答案之前，自己先尝试编程挑战一下，可以复习一下学到的Python的语法。

第6题

求1到100自然数的“和的平方”与“平方和”的差。

def sum_square_diff(n):
    sum_of_squares = sum(map(lambda a:a*a, range(1, n+1)))
    square_sum = sum(range(1, n+1)) ** 2
    return square_sum - sum_of_squares

print(sum_square_diff(100))
1
2
3
4
5
6

第7题

求第10001个素数。

这里就不自己写筛子求素数算法了，直接用primePy模块。

from primePy import primes
def nth_prime(n):
	return primes.first(n)[-1]

print(nth_prime(10001))
1
2
3
4
5

第8题

在1000位的大整数里找到相邻的13个数字，使其乘积最大。

import math

digits = ''.join([
    "73167176531330624919225119674426574742355349194934",
    "96983520312774506326239578318016984801869478851843",
    "85861560789112949495459501737958331952853208805511",
    "12540698747158523863050715693290963295227443043557",
    "66896648950445244523161731856403098711121722383113",
    "62229893423380308135336276614282806444486645238749",
    "30358907296290491560440772390713810515859307960866",
    "70172427121883998797908792274921901699720888093776",
    "65727333001053367881220235421809751254540594752243",
    "52584907711670556013604839586446706324415722155397",
    "53697817977846174064955149290862569321978468622482",
    "83972241375657056057490261407972968652414535100474",
    "82166370484403199890008895243450658541227588666881",
    "16427171479924442928230863465674813919123162824586",
    "17866458359124566529476545682848912883142607690042",
    "24219022671055626321111109370544217506941658960408",
    "07198403850962455444362981230987879927244284909188",
    "84580156166097919133875499200524063689912560717606",
    "05886116467109405077541002256983155200055935729725",
    "71636269561882670428252483600823257530420752963450",
])

def max_prod(adjacent_numbers):
    maxp = 0
    for i in range(len(digits) + 1 - adjacent_numbers):
        x = digits[i : i + adjacent_numbers]
        prod = math.prod(map(lambda c:int(c), x))
        if prod > maxp:
            maxp = prod
    return maxp


print(max_prod(13))
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
28
29
30
31
32
33
34
35
36

可以把for语句用列表解析式改写：

def max_prod(adjacent_numbers):
    numbers = [digits[i : i + adjacent_numbers] for i in range(len(digits) + 1 - adjacent_numbers)]
    prods = [math.prod(map(lambda c:int(c), x)) for x in numbers]
    return max(prods)
1
2
3
4

一行流可以写成这样：

max_prod = max(math.prod(map(lambda c:int(c), digits[i:i + 13])) for i in range(len(digits) + 1 - 13))
1

第9题

找到和为1000的勾股数，并求积。

triples = [(a, b, 1000-a-b) for a in range(1,1000 ) for b in range(a,1000) if a*a+b*b==(1000-a-b)**2]
a, b, c = triples[0]
print(a * b * c)
1
2
3

第10题

求小于2百万的所有素数之和。

用primePy模块实现，发现奇慢无比。

from primePy import primes

ps = primes.upto(2_000_000)
print(sum(ps))
1
2
3
4

从网上找一段经典筛子算法，快多了。

def primes(n):
    """ Returns  a list of primes < n """
    sieve = [True] * n
    for i in range(3,int(n**0.5)+1,2):
        if sieve[i]:
            sieve[i*i::2*i]=[False]*((n-i*i-1)//(2*i)+1)
    return [2] + [i for i in range(3,n,2) if sieve[i]]

print(sum(primes(2_000_000)))
1
2
3
4
5
6
7
8
9