Project Euler 11解题报告

题目: In the 2020 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 any direction (up, down, left, right, or diagonally) in the 2020 grid? 中文题目: 在以下这个2020的网格中,四个处于同一对角线上的相邻数字用红色标了出来: 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 这四个数字的乘积是:26 63 78 14 = 1788696. 在这个2020网格中,处于任何方向上(上,下,左,右或者对角线)的四个相邻数字的乘积的最大值是多少? 解题分析: grid = [ 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 1 ...

阅读全文 »

Project Euler 10解题报告

题目:

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.

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

解题分析: 前面有个题目已经有了好的处理素数的方式,这次直接用前面的代码来实现。

limit = 1000000 
arr = [True] * limit
def sieve(x): 
    global arr,limit 
    for i in range(x*2,limit,x):
        arr[i] = False 
map(sieve, range(2,limit**1/2))
primes = []
for i in range(2,limit):
    if arr[i]: 
        primes.append(i) 
sum = 0 
for p in primes: 
    sum += p 
print sum 

阅读全文 »

Project Euler 9解题报告

题目: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的乘积。 分析: 从 a b c以及 a + b + c = 1000的条件可以看出来a最大不会超过333,b不会超过500,因此代码如下: for x in range(1,332): for y in range(x,499): z=(x*x+y*y)**0.5 if x+y+z==1000: print x*y*z ...

阅读全文 »

project euler 7解题报告

problem 7: 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 10001st prime number? 版本一: 最原始的解法,花费的时间大概要20分钟左右。 import time i=3 num=1 start=time.time() while 1: for j in range(2,i): if i%j==0: break elif j==i-1: num=num+1 break else: continue if num==10001: print i break i=i+1 end=time.time() print end-start 版本二: 优化后的解法,花费时间大概是55秒左右。 import time i=3 num=1 S=[2] length=len(S) start=time.time() while 1: for j in S[0:length/2+1]: if i%j==0: break elif j==S[length/2]: S.append(i) length=length+1 break else: continue if length==10001: print S[10000] break i=i+2 end=time.time() print end-start 版本三: 进一步优化的解法,减少每次需要相除的个数,时间可以优化到不到3秒。 import time, math i=3 num=1 S=[2] length=len(S) start=time.time() while 1: l=int(math.ceil(math.sqrt(length))) for j in S[0:l]: if i%j==0: break elif j==S[l-1]: S.append(i) length=length+1 break else: continue if length==10001: print S[10000] break i=i+2 end=time.time() print end-start import time, math def findprimefactor(num): primefactor=[2,3,5,7] i=9 while len(primefactor) num: flag=True q=int(math.sqrt(i)) k=0 while(primefactor[k] =q): p=primefactor[k] if not(i%p): flag=True break else: flag=False k+=1 if not flag: primefactor.append(i) i+=2 return primefactor if __name__=='__main__': start=time.time() result=findprimefactor(10001) print result[-1],"sec:",time.time()-start 版本四:利用埃拉托色尼选筛法来进行计算,花费的时间大概是0.8秒左右。 import math , time limit=200000 L=[True]*limit start=time.time() def seive(x): for i in xrange(x*2,limit,x): L[i]=False map(seive,[2]) map(seive,xrange(3,int(math.ceil(math.sqrt(limit))),2)) primer=[] for i in xrange(2,limit): if L[i]: primer.append(i) print primer[10000] print time.time()-start ...

阅读全文 »

Project Euler 3解题报告

题目:The prime factors of 13195 are 5, 7, 13 and 29.


What is the largest prime factor of the number 600851475143 ?


题目3:找出一个合数的最大质数因子
13195的质数因子有5,7,13和29.


600851475143的最大质数因子是多少?


<a href="http://projecteuler.net/problem=3" target="_blank">Project Euler problem 3</a>


版本一:


先找出素数,然后确定最大的素因数。时间大概为37秒左右,属于很自然的但是效率很低的方法



import time, math
def findprimefactor(maxnum):
primefactor=[2,3,5,7]
i=9
while i flag=True
q=int(math.sqrt(i))
k=0
while(primefactor[k] p=primefactor[k]
if not(i%p):
flag=True
break
else:
flag=False
k+=1
if not flag:
primefactor.append(i)
i+=2
return primefactor


if __name__=='__main__':
strart=time.time()
L=findprimefactor(775147)
for num in L[::-1]:
if 600851475143%num==0:
print num
break
else:
print 600851475143
print time.time()-strart



版本二:


这个方法是利用除2外所有的素因数都是奇数的特点来完成,简单而且效率很高,时间为0.002秒



import time
strart=time.time()
d, n = 3, 600851475143
while (d * d &amp;lt; n):
if n % d == 0:
n /= d
else: d += 2
print n
print time.time()-strart

阅读全文 »

Project Euler 4解题报告

题目4:找出由两个三位数乘积构成的回文。 一个回文数指的是从左向右和左右向左读都一样的数字。最大的由两个两位数乘积构成的回文数是9009 = 91 * 99. 找出最大的有由个三位数乘积构成的回文数。 project euler problem 4   代码: [python] #!/usr/bin/env python # -*- coding: utf-8 -*- import time strart=time.time() result=0 for num1 in range(999,99,-1): for num2 in range(num1,99,-1): n=num1*num2 if ''.join(reversed(str(n))) is str(n): if n>result: result=n print result print time.time()-strart [/python]

阅读全文 »

Project Euler 2解题报告

题目2:在斐波那契数列中,找出4百万以下的项中偶数项之和。
斐波那契数列中的每一项被定义为前两项之和。从1和2开始,斐波那契数列的前十项为:
1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
考虑斐波那契数列中数值不超过4百万的项,找出这些项中偶数项之和。
Project Euler Problem 2   代码:
a=[1,2,3,5,8,13,21,34,55,89]
while a[-1]+a[-2]&lt;4000000:
a.append(a[-1]+a[-2])
sum([i for i in a if not i%2])

阅读全文 »

Project Euler 1解题报告

题目1:找出1000以下自然数中3和5的倍数之和。


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


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


project euler problem 1:



代码:


sum(list(set([i for i in range(1000) if not i%3 or not i%5 ])))




阅读全文 »

Project Euler 8解题报告

 

Find the greatest product of five consecutive digits in the 1000-digit number.

中文题目:找出以下这个1000位的整数中连续5个数字的最大乘积。

73167176531330624919225119674426574742355349194934
96983520312774506326239578318016984801869478851843
85861560789112949495459501737958331952853208805511
12540698747158523863050715693290963295227443043557
66896648950445244523161731856403098711121722383113
62229893423380308135336276614282806444486645238749
30358907296290491560440772390713810515859307960866
70172427121883998797908792274921901699720888093776
65727333001053367881220235421809751254540594752243
52584907711670556013604839586446706324415722155397
53697817977846174064955149290862569321978468622482
83972241375657056057490261407972968652414535100474
82166370484403199890008895243450658541227588666881
16427171479924442928230863465674813919123162824586
17866458359124566529476545682848912883142607690042
24219022671055626321111109370544217506941658960408
07198403850962455444362981230987879927244284909188
84580156166097919133875499200524063689912560717606
05886116467109405077541002256983155200055935729725
71636269561882670428252483600823257530420752963450

分析:

from string import whitespace 
from operator import mul 
data = open('/tmp/data') # Number pasted to file. 
nos = [int(c) for line in data for c in line if c not in whitespace] 
print max([reduce(mul, nos[i:i+5]) for i in range(len(nos)-5)]) 

阅读全文 »

linux命令gpm参数以及用法详解

gpm作用: 设置鼠标的粘贴功能 gpm语法: gpm [参数] gpm参数: -b 数字 设置每秒的波特率 -B 数字 设置按钮顺序,123,是正常顺序,321适合惯用左手的人使用 -d 出错模式 -h 显示在线帮助 -m 文件名 开启鼠标配置文件 -t 鼠标种类 设置鼠标种类 gpm示例: 启动PS/2鼠标 gpm -t ps2 ...

阅读全文 »