欧拉工程第九解

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

a2 + b2 = c2

For example, 32 + 42 = 9 + 16 = 25 = 52.

There exists exactly one Pythagorean triplet for which a + b + c = 1000. Find the product abc.

解:

1
2
3
4
5
6
7
8
9
10
flag = False
for a in range(1,1000):
for b in range(1,1000):
if a ** 2 + b ** 2 == (1000 - a - b) ** 2:
print a,b,(1000 - a - b)
print a * b * (1000 - a - b)
flag = True
break
if flag:
break

欧拉工程第八解

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

穷举,解:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def MakeProduct(strNum):
prod = 1
for char in strNum:
prod = prod * int(char)
return prod

def GetTheFirstProduct(strNum):
if len(strNum) < 5:
return 0,0
return MakeProduct(strNum[:5]),strNum[1:]

num = '7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450'

largestProduct = 0
while len(num) >= 5:
tmp = GetTheFirstProduct(num)
if tmp == (0,0):
break
num = tmp[1]
if largestProduct < tmp[0]:
largestProduct = tmp[0]
print largestProduct

如果先找到下五个均不为零的连续整数,然后计算它们的积并以之参与比较,效率会更高:

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
def MakeProduct(strNum):
prod = 1
for char in strNum:
prod = prod * int(char)
return prod

def GetTheFirstProduct(strNum):
if len(strNum) < 5:
return 0,0
subStr = strNum[:5]
index = subStr.rfind('0')
if index == -1:
return MakeProduct(subStr),strNum[1:]
else:
return GetTheFirstProduct(strNum[index+1:])

num = '7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450'

largestProduct = 0
while len(num) >= 5:
tmp = GetTheFirstProduct(num)
if tmp == (0,0):
break
num = tmp[1]
if largestProduct < tmp[0]:
largestProduct = tmp[0]
print largestProduct

欧拉工程第七解

第七解:

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?

穷举,并加以最大程度的优化:对大于2的素数,只判断奇数;判断一个奇数是否素数时,只拿已经找到的素数中小于第这个数平方根的数来相除,如果均不能整除,就是素数。Python的实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def IsPrimeNum(num,feed):
from math import sqrt
tmp = feed[:]
while tmp[-1] > int(sqrt(num)):
tmp.pop()
for i in tmp:
if num % i == 0:
return False
return True

limit = 10001
feed = [2,3,5,7]
temp = 7
counter = 4
while counter < limit :
temp += 2
if IsPrimeNum(temp,feed):
feed.append(temp)
counter += 1
print temp

执行了一下,在我这里居然用了五百秒才出结果,神啊,差不多十分钟啊。想到PHP号称速度很快,于是用PHP重新实现了一下:

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
function IsPrimeNum($num,$feed){
$base = floor(sqrt($num));
foreach($feed as $i=>$v){
if($v > $base){
return true;
}
if($num % $v == 0){
return false;
}
}
}

$limit = 10001;
$feed = array(2,3,5,7);
$counter = 4;
$tmp = 7;
while($counter < $limit){
$tmp += 2;
if(IsPrimeNum($tmp,$feed)){
$counter++;
$feed[] = $tmp;
}
}

echo $tmp;

还好,七十四秒出结果,看来PHP的牛皮不是吹的。当然,Lua会更快:

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
function IsPrimeNum(num,feed)
require('math')
local limit = math.floor(math.sqrt(num))
for i,v in ipairs(feed) do
if v > limit then
return true
end
if num % v == 0 then
return false
end
end
end

local limit = 10001
local feed = {2,3,5,7}
local counter = 4
local tmp = 7
while counter < limit do
tmp = tmp + 2
if IsPrimeNum(tmp,feed) then
counter = counter + 1
table.insert(feed,tmp)
end
end

print(tmp)

执行完后还是吓了一跳,0.3秒,同样是语言,效率的差别咋就那么大呢?!我在想用Java会不会算到2009去。

我不相信这道题用Python就那么难解,下面是用递归实现的程序:

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
from math import sqrt

def GuessPrime(feed,limit):
if feed == 2 :
return [2]
elif feed == 3 :
return [2,3]

tmp = int(sqrt(feed))
primes = GuessPrime(tmp,limit)

base = 0
if tmp % 2 == 0:
base = tmp + 1
else:
base = tmp
for i in range(base,feed,2):
flag = 0
for j in primes:
if i % j == 0:
flag = 1
break
if flag == 0:
primes.append(i)
if len(primes) == limit:
return primes

return primes

limit = 10001
feed = 1000000
primes = GuessPrime(feed,limit)
print primes[limit-1]

11秒就出了结果,说到底,算法的改进才是硬道理!

欧拉工程第六解

第六解:

The sum of the squares of the first ten natural numbers is, 12 + 22 + … + 102 = 385

The square of the sum of the first ten natural numbers is, (1 + 2 + … + 10)2 = 552 = 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
3
4
5
6
sumSquare = 0
sum = 0
for i in range(1,101):
sumSquare += i**2
sum += i
print sum**2 - sumSquare

欧拉工程第五解

第五解:

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 number that is evenly divisible by all of the numbers from 1 to 20?

解:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#为简洁明了,此处不作校验
def GetGreatestCommonDivisor(min,max):
'''辗转相除法求最大公约数'''
while min > 0:
tmp = min
min = max % min
max = tmp
return max

def GetLeastCommonMultiple(a,b):
if a > b:
max = a
min = b
else:
max = b
min = a
div = GetGreatestCommonDivisor(min,max)
return min * max / div

temp = 1
for i in range(1,21):
temp = GetLeastCommonMultiple(i,temp)
print temp

本题旨在求最小公倍数。此算法有意思的是,它的精华在于如何求解两个正整数的最大公约数,有点围魏救赵的意思。

这里可以找到另外一些求解最小公倍数的方法。

欧拉工程第四解

第四解:

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.

解:

1
2
3
4
5
6
7
largestPalindrome = 0
for i in range(100,1000):
for j in range(100,1000):
product = i * j
if int(str(product)[::-1]) == product and product > largestPalindrome:
largestPalindrome = product
print largestPalindrome

穷举,有没有效率高的办法?

欧拉工程第三解

第三解:

The prime factors of 13195 are 5, 7, 13 and 29. What is the largest prime factor of the number 600851475143 ?

解:

1
2
3
4
5
6
7
8
9
10
11
feed = 600851475143

def GetFactor(feed,footmark):
while footmark < feed:
footmark += 2
if feed % footmark == 0:
print footmark
GetFactor(feed / footmark,footmark)
break

GetFactor(feed,1)

欧拉工程第二解

第二解:

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, … Find the sum of all the even-valued terms in the sequence which do not exceed four million.

解:

1
2
3
4
5
6
7
8
9
10
i = 1
j = 2
sum = 0
while j < 4000000 :
if j % 2 == 0 :
sum = sum + j
t = i
i = j
j = t + j
print sum

欧拉工程第一解

欧拉工程”是一个很有意思的网站,它每周会提供一道数学题,要求访问者使用任一种编程语言设计一个计算机程序求解。到现在为止已经出了二百一十一道题,当然,题的难度是依次递增的。几十个国家的程序员已参与了这个工程,截至目前,中国有四百多人参与,但是解决所有的二百多道题的只有一个人。

我觉得没事儿的时候做一道很有意思,下面是第一道,很简单:

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.

最容易想到的一算法就是依次取出一到一千的整数,只要是三或五的倍数,就累加起来,最终的和就是结果:

1
2
3
4
5
6
7
sum = 0

for num in range(1,1000):
if not (num % 3 != 0 and num % 5 != 0):
sum += num

print sum

但是我觉得这个算法太普通了,从一到一千要做一千次循环,时间复杂度会比较高。所以我设想只取出三和五的倍数,然后相加就行了,所需要考虑的只是怎么处理三和五的公倍数的问题。下面是我的算法,只有三百多次循环:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def SumMultiple(feed,limit):
threeMultiple = 3 * feed
fiveMultiple = 5 * feed

if threeMultiple >= limit:
return None
if fiveMultiple >= limit:
return threeMultiple
if fiveMultiple % 3 == 0:
return threeMultiple

return threeMultiple + fiveMultiple

sum = 0

for feed in range(1,500):
if SumMultiple(feed,1000) == None:
break;
sum += SumMultiple(feed,1000)

print sum

不过事与愿违,通过测试,这个算法的效率要比上一种低,我想应该是SumMultiple()函数中运算和比较次数较多导致的。

不管怎样,第一个问题已经顺利解决了:

为rxvt-unicode开启标签和链接支持

写完urxvt-unicode快速上手,本以为已将urxvt的用法一网打尽,不料AndyWxy网友又找到了两个新的功能:使urxvt启用标签和在urxvt中打开网页链接。

标签功能很实用,一般为了达到复用终端窗口的目的会采用两种方式:一是配合screen使用,另一个就是启用标签。然而前者有一个缺点就是不直观,标签页恰好能弥补这个缺陷。urxvt不愧是个功能强大的终端工具,如果在编译时开启perl支持,则urxvt可启用多标签功能。用法如下:

一是在启动的时候加入命令行参数:

urxvt -pe tabbed

二是在配置文件“.Xresources”中添加如下配置信息:

URxvt.perl-ext-common: default,tabbed

则默认情况下执行urxvt就会打开多标签功能。urxvt的标签支持使用鼠标操作,同时可以使用Ctrl+Shift+左右箭头来切换标签页,使用Ctrl+Shift+向下箭头开启新标签。

另外一个功能就是可以通过在urxvt中的链接上点击鼠标左键来通过设定的浏览器打开之。首先在“.Xresources”文件中添加如下内容:

URxvt.urlLauncher: firefox URxvt.matcher.button: 1

然后使用如下命令打开urxvt:

urxvt -pe matcher

即可。也可以在配置文件中添加上述内容之后再添加一行:

URxvt.perl-ext-common: matcher

此后即默认开启在终端窗口中打开链接的功能。注意修改“.Xresources”文件后需要执行如下命令才能使修改后的配置文件生效:

xrdb ~/.Xresources