欧拉工程第一至十题解题思路分析

一、3或5的倍数

如果我们将小于10的所有是3或5倍数的自然数列出来,我们得到3,5,6和9,它们的和是23。与之类似,计算1000以下所有是3或5的倍数的自然数的和。

分析:此题解法较为直接,将1000以下所有3或5的倍数列出再求即可,以下代码使用了python的列表推导式以简化代码结构。

sum([x for x in range(1,1000) if x%3==0 or x%5==0])

二、偶数斐波那契数

斐波那契序列中的数都是由前两项加总得出,假设第一与第二项为1与2,则前十项分别为:

$$ 1,2,3,5,8,13,21,34,55,89 $$
考虑不超过四百万的斐波那契数,计算其中偶数斐波那契数的和。

分析:首先编写一个函数,这个函数计算小于等于给定N的斐波那契数,然后筛选出其中的偶数并求和。

def fibs_below(n,a=1,b=2):
    fib = [a,b]
    while True:
        a,b = b,a+b
        if b <= n:
            fib.append(b)
        else:
            return fib

sum([x for x in fibs_below(4e6) if x%2==0])

三、最大质因数

13195的质因数分别为5,7,13与29,600851475143最大的质因数是多少?

分析:求解质因数的方法较多,最常用的方法为短除法,即对于任意大于2的自然数N,先用N除以2,再用所得之商即(N/2)再除以2,直到商不能为2所整除,此时将被除数加一并比较其平方是否小于被除数,如果小于则再用商除以3,如不能整除,则除以5(因为所有2的倍数即偶数因数已在第一轮不断除以2时被排除了,所以之后都要加二)。这样循环下去直到除数的平方不再小于被除数,则退出循环,最后得到的N即为最大的质因数。实际执行中,要分两层循环,外层循环判断除数的平方是否小于被除数,内层循环判断被除数是否可以整除除数。

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

max_prime_factor(600851475143)

四、最大回文数乘积

回文数即从正反两边读都是一样的数,两个二位数的乘积中最大的回文数为\(9009=91*99\),寻找两个三位数乘积中最大的回文数。

分析:编写一个函数判断给定的数是否为回文数,即首先将数转化为字符串,再看该字符串与其逆转是否同一,如果同一则为回文数。然后在999至100的三位数做两两守相乘,从中筛选回文数并求最大值。

r = range(999,99,-1)
is_palindrome = lambda x : str(x) == str(x)[::-1]
max([i*j for i in r for j in r if is_palindrome(i*j)])

五、最小公倍数

2520是可以被从一到十所有自然数整除的最小的数,即为从一到十的自然数的最小公倍数,求从一到二十所有自然数的最小公倍数。

分析:根据欧几里德公式,我们可以两个数最大公约数推出两个数的最小公倍数,即对于任意自然数\(a,b\),设两个数的最大公约数为\(gcd(a,b)\),则两个数的最小公倍数

$$ lcm(a,b)=\frac{ab}{gcd(a,b)} $$

据此,我们可以先求出两个数的最小公倍数,再用这个最小公倍数与第三个数求最小公倍数,从而迭代得出\(N\)个数的最小公倍数。代码中从外部库中导入了python中求最大公约数的函数,并利用reduce()函数迭代求出多个数的最小公倍数。

from fractions import gcd

def lcm(numbers):
    def lcm(a, b):
        return (a * b) // gcd(a, b)
    return reduce(lcm, numbers)

lcm(range(1,21))

六、和的平方与平方的和之间的差值

前十个自然数的平方的和为:

$$ 1^2+2^2+3^2+\cdots+10^2=385 $$
而前十个自然数和的平方为:
$$ (1+2+3+\cdots+10)^2=55^2=3025 $$
两者的差为\(3025-385=2640\),求前一百个自然数的和的平方与平方的和之间的差值。

分析:此题至少有两种解法:第一种解法为求各公式法,因为自然数的和以及平方的和都有相应的求和公式,可以根据公式直接推出两者差值的计算公式;第二种方式即为直接计算并求差值,因为计算量不大,这里使用第二种方法。

arr = [x**2 for x in range(1,101)]
res = (sum(range(1,101)))**2 - sum(arr)

七、第10001个质数

列出前六个质数,我们可以发现第六个质数为13,那么第10001个质数是多少?

分析:一般而言,对于第\(n\)个素数\(p_n\),满足以下不等式(参见素数计数函数):

$$ ln(nln(n))-1<\frac{p_n}{n}<ln(nln(n)) $$

在这里我们只关注上界,则可以得到\(p_n<nln(nln(n))=nln(n)+nln(ln(n))\),我们先筛选出从2到上界的所有质数,再取其中的第10001个质数,即得到结果。

from sympy import sieve
from math import log,ceil

def nth_prime(n):
    up_bound = ceil((log(n)+log(log(n))) * n)
    primes = list(sieve.primerange(1,up_bound))
    return primes[n-1]

nth_prime(10001)

八、序列中的最大乘积

在下面1000位数中,连续四个数的最大乘积为\(9*9*8*9=5832\):

IMG

寻找连续十三数的最大乘积,这个乘积是多少?

分析:此题解题思路较为直接,分为以下步骤:1)将以上数字存入到TXT文件中,用python导入并存入到一个LIST中;2)从LIST中第0位开始直到第987位,依次求连续十三位数的乘积并存入到结果LIST中;3)求结果LIST的最大值得到结果。

data = ''
f = open("euler/ep08.txt")
for line in f.readlines():
    data = data + line.strip()

res = []
for i in range(988):
    sub = [int(x) for x in data[i:i+13]]
    prod = reduce(lambda x,y:x*y, sub)
    res.append(prod)

max(res)

九、特殊的毕达哥拉斯三元数

毕达哥拉斯三元数是指一类三个自然数的集合,其中\(a<b<c\)\(a^2+b^2=c^2\),例如\(3^2+4^2=5^2\)。仅存在一组毕达哥拉斯三元数使得\(a+b+c=1000\),求\(abc\)

分析:根据欧几里德公式,对于\(m>n>0,a=m^2-n^2,b=2mn,c=m^2+n^2\)构成毕达哥拉斯三元数,则有\(a+b+c=m^2-n^2+2mn+m^2+n^2=2m^2+2mn=2m(m+n)=1000\),即\(m(m+n)=500\),可以看出\(m<m+n\)\(m,n\)都是\(500\)的因数,则\(m<\sqrt{500}\approx22.36\),则可以从22依次递减一进行尝试,寻找500的因数,到20时寻找结束,得到\(n=5\),则跳出循环。最后,根据以下欧几里德公式计算\(abc\)

from math import sqrt

def find_pytha():
    upBoundary = int(sqrt(500)) + 1
    for i in range(upBoundary,1,-1):
        if 500%i == 0:
            n = 500/i - i
            if i > n:
                return i,n

i,n = find_pytha()
a = i**2 + n**2
b = 2*i*n
c = i**2 - n**2
print(a*b*c)

十、质数的和

\(10\)以下的质数的和为\(2+3+5+7=17\),求所有两百万以下的质数的和。

分析:首先筛选出两百万以下的质数,然后求和即可:

from sympy import sieve
print(sum(list(sieve.primerange(1,2e6))))