欧拉计划Python解法（第1题-第5题）

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

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

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

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

第1题

问题：
求小于1000的能被3或5整除的所有整数之和。

第一种解法：

s = 0
for i in range(1000):
    if i % 3 == 0 or i % 5 == 0:
        s += i
print(s)
1
2
3
4
5

第二种解法：
利用列表推导式，可以用一行解决问题。

s = sum([i for i in range(1000) if i % 3 == 0 or i % 5 == 0])
print(s)
1
2

第三种解法：
用lambda函数。

s = sum(filter(lambda x:x%3==0 or x%5==0, range(1000)))
print(s)
1
2

第2题

问题：
求400万之内所有偶数的斐波那契数字之和。

一种朴素的解法：

fib = [1, 2]
i = 2
s = 2
while True:
    c = fib[i-1] + fib[i-2]
    if c >= 4_000_000:
        break
    fib.append(c)
    if c % 2 == 0:
        s += c
    i += 1

print(s)
1
2
3
4
5
6
7
8
9
10
11
12
13

Python里的列表支持负索引，所以可以改为：

fib = [1, 2]
s = 2
while True:
    c = fib[-1] + fib[-2]
    if c >= 4_000_000:
        break
    fib.append(c)
    if c % 2 == 0:
        s += c

print(s)
1
2
3
4
5
6
7
8
9
10
11

可以用lambda函数：

fib = [1, 2]
while True:
    c = fib[-1] + fib[-2]
    if c >= 4_000_000:
        break
    fib.append(c)

s = sum(filter(lambda x:x%2==0, fib))
print(s)
1
2
3
4
5
6
7
8
9

利用Python的生成器的语法，还可以这样写：

def fib(limit):
    a, b = 1, 2
    while a <= limit:
        yield a
        a, b = b, a + b

s = sum(filter(lambda x:x%2==0, fib(4_000_000)))
print(s)
1
2
3
4
5
6
7
8

第3题

问题：
找出整数600851475143的最大素数因子。

根据题意，很快可以写出代码：

def is_prime(num):
    for i in range(2, num // 2 + 1):
        if num % i == 0:
            return False
    return True

# 这个算法的效率太差
big_num = 600851   # 600851475143 如果用这个大数很长时间运行不出来结果
for i in reversed(range(2, big_num)):
    if big_num % i == 0 and is_prime(i):
        print(i)
        break
1
2
3
4
5
6
7
8
9
10
11
12

上面的代码逻辑上没问题，但几分钟也运行不出来结果，试着把数字调小一点，比如：600851，不到1秒出来结果，看来程序的效率太差了，主要原因在于判断素数的运算量太大，需要优化算法。

可以尝试把大数进行素数因子分解，找到一个素因子之后，可以用除法缩小搜索的范围，效率得到大幅提升，不到1秒得出结果。优化后的代码：

def is_prime(num):
    for i in range(2, num // 2 + 1):
        if num % i == 0:
            return False
    return True


big_num = 600851475143
max_prime_factor = 2

while big_num >= 2:
    for i in range(2, big_num + 1):
        if big_num % i == 0 and is_prime(i):
            big_num //= i
            if i > max_prime_factor:
                max_prime_factor = i
                print('大因子：', max_prime_factor)
                break
            
print(max_prime_factor)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

网上给出的更好的写法：

def largest_prime_factor(n):
    i = 2
    while i * i <= n:
        if n % i:
            i += 1
        else:
            n //= i
    return n

print(largest_prime_factor(600851475143))
1
2
3
4
5
6
7
8
9
10

下面的这段代码可以找出所有的因子：

def prime_factors(n):
    i = 2
    factors = []
    while i * i <= n:
        if n % i:
            i += 1
        else:
            n //= i
            factors.append(i)
    if n > 1:
        factors.append(n)
    return factors

print(prime_factors(600851475143))
1
2
3
4
5
6
7
8
9
10
11
12
13
14

如果安装了primePy模块，则可以这样：

from primePy import primes
print(primes.factors(600851475143)[-1])
1
2

第4题

所谓回文数，就是两边读都一样的数，比如：698896。
求两个3位数之积最大的回文数。

解法1：

# 判断回文数
def is_palindromic(n):
    s = str(n)
    return s == s[::-1]


max_prod = 0
for a in range(100, 1000):
    for b in range(100, 1000):
        c = a * b
        if is_palindromic(c) and c > max_prod:
            max_prod = c

print(max_prod)
1
2
3
4
5
6
7
8
9
10
11
12
13
14

解法2：
用列表推导式和filter函数。

# 判断回文数
def is_palindromic(n):
    s = str(n)
    return s == s[::-1]


prod = [a*b for a in range(100,1000) for b in range(100,1000)]
max_prod = max(filter(is_palindromic, prod))
print(max_prod)
1
2
3
4
5
6
7
8
9

这种算法不是效率最高的，因为它会把所有乘积都计算出来，并依次进行回文数的判断。

第5题

找出能够被1, 2, 3, …, 20整除的最小整数。

直接根据题意暴力搜索：

def can_divide_1_20(x):
    for n in range(2, 21):
        if x % n:
            return False
    return True

x = 20
while not can_divide_1_20(x):
    x += 2

print(x)
1
2
3
4
5
6
7
8
9
10
11

这个算法的效率非常差。

运用一点数学知识改进一下，先找出所有因子，再将因子合并，最后求积即可，效率提升无数倍。

from primePy import primes

def counts(items):
    cs = dict()
    for i in items:
        cs[i] = cs.get(i, 0) + 1
    return cs


# https://www.pythonlikeyoumeanit.com/Module2_EssentialsOfPython/Problems/MergeMaxDicts.html
def merge_max_mappings(*dicts):
    """ 合并字典，相同的键保留最大的值
    例如：
    dict1 = {'a':1, 'b':4}
    dict2 = {'a':3, 'c':5}
    合并之后为：
    {'a': 3, 'b': 4, 'c': 5}
    """
    merged = {}
    for d in dicts:  # `dicts` is a tuple storing the input dictionaries
        for key in d:
            if key not in merged or d[key] > merged[key]:
                merged[key] = d[key]
    return merged


dicts = []
for n in range(2, 21):
    all_factors = primes.factors(n)
    cs = counts(all_factors)
    dicts.append(cs)

m = merge_max_mappings(*dicts)
print(m)

prod = 1
for k, v in m.items():
    prod *= pow(k, v)
print(prod)
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
37
38
39

还可以利用collections模块，改写一下：

from primePy import primes
import collections
import math

# 这里省略了前面的 merge_max_mappings() 函数


dicts = [collections.Counter(primes.factors(n)) for n in range(2, 21)]
merged = merge_max_mappings(*dicts)
prod = math.prod([pow(k, v) for k, v in merged.items()])
print(prod)
1
2
3
4
5
6
7
8
9
10
11