首页 > Project Euler > Project Euler个人解答(Problem 1~10)

Project Euler个人解答(Problem 1~10)

2013年12月16日 发表评论 阅读评论

pe_banner_light

写在前面:

毅然决然决定开这个坑!!好吧,本文主要为个人做笔记用,也可以方便大家交流,但是做题时为了节省时间,代码写得有些乱,思路有时也比较粗暴,方法和变量命名请不要吐槽。。我看过讨论版上有很多精彩的方法,但是这里只做一个自己的笔记用而已!!

题目翻译摘自Project Euler 中文翻译站,特此感谢,虽然我做题的时候都是看英文的。。

另外,题目里面有些数学上的东西,比如说平方那些,我就懒得修改了。。看得懂就行。 

再另外,虽然我一般的习惯是不分P来写博客,也就是说一个主题就开一篇,比如我以前写的所有的笔记性质的博客,全是一篇超长的,但是有人跟我说这样看起来挺累的,所以我也就决定分一下P,正好博客搬家,水一下数量给搜索引擎看。。。而且,被我搞到现在每一道题的解答的格式有点复杂,所以也是为了保险起见,我还是分一下P吧,不然哪一天WP抽风了,一打开修改后全部格式全乱了就神作了。。。老师教导我们,鸡蛋不要放在一个篮子里!!

前言部分就这么多吧~每10题1P,前面30到40题都是超级简单的。。。
顺带提一下,如果有谁发现里面有错,麻烦告知一声,我总感觉不可能没搞错。。


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.

翻译:

10以下的自然数中,属于3和5的倍数的有3,5,6和9,它们之和是23.

找出1000以下的自然数中,属于3和5的倍数的数字之和。

思路:

法一:暴力解决
法二:3的倍数的和加上5的倍数的和减去15的倍数的和

Code:Mathematica

法一:
m = 1000;
Total@Union@Flatten@Append[Range[3, m - 1, 3], Range[5, m - 1, 5]]
法二:
Total[#] & /@ {Range[3, m - 1, 3], Range[5, m - 1, 5], -Range[15, m - 1, 15]} // Total

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, ...

考虑斐波那契数列中数值不超过4百万的项,找出这些项中值为偶数的项之和。

思路:

暴力解决,事实上,可以发现3的整数倍的项才是偶数!!

Code:Mathematica

Total@Select[
  Table[Fibonacci[i + 1], {i, 1, 
    NestWhile[# + 1 &, 1, Fibonacci[#] < 4000000 &]}], EvenQ]

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的最大质数因子是多少?

思路:

暴力解决

Code:Mathematica

Sort[FactorInteger[600851475143], First &] // Last // First

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.

找出最大的有由个三位数乘积构成的回文数。

思路:

基本可以认为结果必然是6位数,所以形式是:

\(100000a+10000b+1000c+100c+10b+a\\=100001a+10010b+1100c\\=11(9091a+910b+100c)\)

所以必然有一个数可以被11整除!然后再扫描全局

Code:Mathematica

palindromicQ[n_] := (Characters[ToString[n]] // Reverse) === Characters[ToString[n]];
list=Table[i*j, {i, 100, 999}, {j, 110, 999, 11}] // Flatten
Select[list, palindromicQ[#] &] // Sort // Last

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~20所有里面每个质因数的最高的次,比如2的最高必然就是四次,3最高两次之类的,然后直接相乘。

Code:Mathematica

Times @@ Power @@@ 
  Function[p, (Select[
        Flatten[FactorInteger /@ Range[2, 20], 1], #[[1]] == p &]~
       SortBy~Last) // Last] /@ Select[Table[i, {i, 2, 20}], PrimeQ]

Problem 6:Sum square difference

The sum of the squares of the first ten natural numbers is,

\(1^2 + 2^2 + ... + 10^2 = 385\)

The square of the sum of the first ten natural numbers is,

\((1 + 2 + ... + 10)^2 = 55^2 = 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.

翻译:

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

\(1^2 + 2^2 + ... + 10^2 = 385\)

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

\((1 + 2 + ... + 10)^2 = 55^2 = 3025\)

所以平方和与和的平方的差是3025-385 = 2640.

找出前一百个自然数的平方和与和平方的差。

思路:

法一:暴力计算
法二:直接用公式:

\(\dfrac{k^2(1+k^2)}{4}-\dfrac{k(k+1)(2k+1)}{6}\)

Code:Mathematica

法一:
m = 100;
Sum[i, {i, 1, m}]^2 - Sum[i^2, {i, 1, m}]
法二:
m = 100;
1/4 m^2 (1 + m)^2 - 1/6 m (m + 1) (2 m + 1)

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?

翻译:

前六个质数是2,3,5,7,11和13,其中第6个是13.

第10001个质数是多少?

思路:

我用Mathematica我自豪!!

Code:Mathematica

Prime[10001]

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个数字的最大乘积。(例如前五个数字的乘积是7*3*1*6*7=882)

思路:

暴力解决

Code:Mathematica

str="题目字符串"
num = ToExpression@Characters@str;
Table[Times @@ Table[num[[i]], {i, j, j + 4}], {j, 1, 996}] // Sort // Last

Problem 9:Special Pythagorean triplet

A Pythagorean triplet is a set of three natural numbers, \(a < b < c\), for which,

\(a^2 + b^2 = c^2\)

For example, \(3^2 + 4^2 = 9 + 16 = 25 = 5^2\).

There exists exactly one Pythagorean triplet for which a + b + c = 1000.

Find the product abc.

翻译:

一个毕达哥拉斯三元组是一个包含三个自然数的集合,a < b < c,满足条件:

\(a^2 + b^2 = c^2\)

例如:\(3^2 + 4^2 = 9 + 16 = 25 = 5^2\).

已知存在并且只存在一个毕达哥拉斯三元组满足条件\(a + b + c = 1000\)

找出该三元组中abc的乘积。

思路:

法一:两边之和大于第三遍,所以每条边必然小于500,假设三条边从小到大为a,b,c,那么a的取值范围是0到500,b就是max(500-a,a)到500,c就是1000-a-b,这样可以大幅减少计算时间。虽然本来就消耗不了多少。

法二:传闻毕达哥拉斯组必然可以写成以下形式:

\(\left\{\begin{array}{lll}a=2mn\\b=m^2-n^2\\c=m^2+n^2\end{array}\right.\)
因为\(a+b+c=1000\),所以:
\(m(m+n)=500\)
\(n=\dfrac{500}{m}-m\)
所以必然有\(m< \sqrt{500}\),所以\(m<23\);
又因为\(m>n\),所以可以计算出\(m=n\)的情况,也就是:\(m=\dfrac{500}{m}-m\),得到\(m=15.81\),所以\(m>16\)
在这个区间内,可以被500整除的m只有20一个,所以\(m=20\),于是可以算出\(n=5\).

法三:这里的结论之后的某道题(p39)会用到,所以现在这里推导吧。。【有点跳步,不过应该跟得上。。】
因为\(a+b=1000-c\)
两边平方:\(2ab=1000^2-2000c=1000^2-2000(1000-a-b)\)
得到\(ab=-500 \times 1000+1000a+1000b\)
所以\(500\times 1000=1000a+(1000-a)b\)
最后得到\(b=1000\dfrac{500-a}{1000-a}\)
这个就是我们手算的结论。。。事实上。。。这个推导还有个更快的方法。。就是。。。EPP9
然后呢,只要扫描a,看b是不是整数就可以了,这个只要一遍,而且加上下面这个条件:
EPP92
a的范围只要扫描1到\(1000-\dfrac{1000}{\sqrt{2}}=292.893\)就可以了~

最后,关于这道题相关资料请查看:http://mathworld.wolfram.com/PythagoreanTriple.html

Code:Python

#法一
for a in range(1,500):
    for b in range(max(500-a,a),500):
        c = 1000-a-b;
        if a*a+b*b==c*c:
            print a*b*c
#法二
#略
#法三
for a in range(1,292):
    b = 1000*(500-a)/(1000-a);
    if b == int(b):
        print a*b*(1000-a-b)

Code:Mathematica

(*一行解决大法*)
Solve[a^2 + b^2 == c^2 && a + b + c == 1000 && 0 < a < b < c, {a, b, c}, Integers]

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.

找出两百万以下所有质数的和。

思路:
法一:暴力解决,Python的话,自己写一个判断质数的函数的话,速度会很慢,我的机子计算需要53秒,快要超过Euler Project的one-minute-problem的界限了。但是用Mathematica的话,就会很快!!

法二:法一瓶颈在于质数判断上,所以可以用最原始的质数筛选法,去掉2的倍数,再去掉3的倍数的方法查找,这样速度可以在2秒内完成!!

Code:Python

#法一
def PrimeQ(n):
    if n <= 1:
        return False
    for i in xrange(2,int(n**0.5+1)):
        if n%i == 0:
            return False;
    return True;

sum = 2;
for i in range(3,2000000,2):
    if PrimeQ(i):
        sum += i;
print sum
#法二
num = 2000000

total = (num-1) * num / 2-1 
primes = [1]*num

m = int(sqrt(num)) + 1

for i in xrange(2, m):
    if primes[i] == 1:
        for j in xrange(i*2, num, i):
            if primes[j] == 1:
                primes[j] = 0
                total -= j
print total

Code:Mathematica

法一:
Total@Select[Range[2000000], PrimeQ]
#法二
#略

【完】

本文内容遵从CC版权协议,转载请注明出自http://www.kylen314.com

  • Saya

    感觉第二题的代码略有些问题Table[Fibonacci[i + 1], {i, 1, NestWhile[# + 1 &, 1, Fibonacci[#] < 4000000 &]}]多列了两项,Fibonacci[34]和Fibonacci[35]只是因为这两项都是奇数,才对结果没影响的

    • 好像是少了个+1,因为题目里面的数列是1,2,3,5...而Mma里面是1,1,2,3,5。。。我说少年,你不搞科研没事来我博客乱混,你老板知道吗。。

      • Saya

        我这不是抱着学习Mathematica的心态,虚心钻研代码么

  • Saya

    不得不说Mathematica真是既简洁又暴力

    • 你也去注册个EP的账号去玩吧,这样进步快一点。。

      • 红薯

        第10题:Tr@Prime@Range@PrimePi@2000000 // AbsoluteTiming

        • 学到PrimePi这个函数了~而且Tr求和可以让代码再短一些,哈哈

      • 红薯

        第5题:LCM @@ Range[20]Product[i^Floor@Log[i, 20], {i, {2, 3, 5, 7, 11, 13, 17, 19}}]

        • 第二个方法真心赞!!我上面写了好几行,没想到可以用这么简洁的方法实现!!高手求继续点评~

      • 红薯

        pe1:Union @@ Range[0, 999, {3, 5}] // TrTr@Pick[#, #~Mod~3 #~Mod~5, 0] &@Range[999]pe3:FactorInteger[600851475143][[-1, 1]]pe4:Select[Union @@ Array[Times, {900, 900}, 100] // Reverse, # == Reverse[#] &@IntegerDigits[#] &, 1]

        • 看了您的代码,我感觉到我的代码里面从C或者Matlab里面遗留下来的代码习惯太重,还没有真正很好的写出很有Mma style的代码!

        • 对了,关于第一题,我在知乎上看到一道题,说计算2*10^8以内2,3,5,7的倍数的和,红薯大大有什么非常简洁的方法么?不用容斥原理的话内存会爆掉,用的话代码怎么写最简洁?

          • 红薯

            可以用“公式法”:Sum[(Boole@Or[i~Mod~2 == 0, i~Mod~3 == 0, i~Mod~5 == 0, i~Mod~7 == 0]) i, {i, n}] /. n -> 10^8Sum[(1 - Unitize[i~Mod~2 i~Mod~3 i~Mod~5 i~Mod~7]) i, {i, n}] /. n -> 10^8

            • 哇,好思路!!

          • 红薯

            不用容斥原理也不一定爆内存的,编译后运行也就几秒cf = Compile[{}, Sum[If[Or[i~Mod~2 == 0, i~Mod~3 == 0, i~Mod~5 == 0, i~Mod~7 == 0], i, 0.], {i, 10^8}], CompilationTarget -> "C", RuntimeOptions -> "Speed" ];cf[] // AccountingForm // AbsoluteTiming

            • 我一开始思路直接一个Range[0,2*^8,2]就爆了。。

      • 红薯

        第10题用筛法更快(不到0.1s),借鉴了Matlab函数primes的算法且更快一点,用了点向量化:primes[n_] := Block[{p = Range[1, n, 2]}, p[ ] = 2; Do[If[p[[(k + 1)/2]] != 0, p[[(k^2 + 1)/2 ;; ;; k]] = 0], {k, 3, n^.5, 2}]; SparseArray ["NonzeroValues"]];Floor@Tr@N@primes[2*10^6] // AbsoluteTiming

        • 一般用Mma就是不想用筛法。。。不过这段代码可以收藏起来,以后速度不够可以拿来试试~

  • WDatou

    第六题的公式有一处小小……的笔误,在“Code : Mathematica”上面一行的公式里面,第二个k的指数2,应该在括号外面。代码中的公式是正确的。我这么做是不是太苛刻了……深刻忏悔中……