我使用硬體Raspberry Pi 2與軟體Raspbian,作為執行速度的依據。
十八世紀數學家Leonhard Euler。
注意:並不提供詳細的說明與分析。
Problem 1: Multiples of 3 and 5,小於1000的正整數中,找出3或5的倍數,相加求總和。
底下函式直接使用暴力法,傳入參數1000可算出此題的答案。
def m35(n):
result = 0
for i in range(1, n):
if i % 3 == 0 or i % 5 == 0:
result += i
return result
也可縮成一行,其中運用了產生器運算式(generator expression)。
def m35(n):
return sum(i for i in range(1, n) if i%3==0 or i%5==0)
Problem 2: Even Fibonacci numbers,找出小於四百萬而且是偶數的費波那契數,相加求總和。
首先是計算費波那契數(fibonacci number)的函式,採取遞迴形式,但會記憶算過的值,免得重複計算。
memo = {0: 0, 1: 1}
def fib(n):
if n not in memo:
memo[n] = fib(n-1) + fib(n-2)
return memo[n]
然後是題目本身,使用暴力法,從小到大算出費波那契數,小於四百萬而且是偶數的話就加起來。底下函式傳入參數4000000,即可得到答案。
def efn(max):
result = 0
n = 1
fn = fib(n)
while fn <= max:
if fn % 2 == 0:
result += fn
n += 1
fn = fib(n)
return result
Problem 3: Largest prime factor,找出600851475143最大的質因數。
首先是能從小到大、不斷給出質數的函式,底下prime_gf是產生器函式,prime_f則是產生器。
def prime_gf():
primes = [2]
def is_prime(n):
for i in primes:
if n % i == 0:
return False
return True
while True:
p = primes[-1]
yield p
while True:
p += 1
if is_prime(p):
primes.append(p)
break
prime_f = prime_gf()
然後是題目本身,底下函式傳入參數600851475143,即可得到答案。
def lpf(n):
max = 1
for i in prime_f:
if i <= n:
while n % i == 0:
n /= i
max = i
else:
break
return max
Problem 4: Largest palindrome product,迴文數,譬如9009,從頭端看過來、與從尾端看過去都一樣,而且9009是兩個2位數相乘後的迴文數中最大的(91 × 99),請問兩個3位數相乘後最大的迴文數是多少。
首先,底下函式可判斷是否為迴文數。
def is_palindrome(n):
ns = str(n)
a, b = 0, len(ns)-1
while a < b:
if ns[a] != ns[b]:
return False
else:
a += 1
b -= 1
return True
然後,底下函式的參數d代表幾位數,以暴力法列出所有的兩個d位數組合,相乘後判斷是不是迴文數,通通記錄起來。
def palindromes(d):
result = []
for x in range(10**d-1, 10**(d-1)-1, -1):
for y in range(x, 10**(d-1)-1, -1):
if is_palindrome(x * y):
result.append((x*y, x, y))
return result
最後進行排序,便可得到最大的迴文數。底下函式傳入參數3可得到答案。
def palindromes_max(d):
return sorted(palindromes(d), key=lambda x: x[0])[-1][0]
Problem 5: Smallest multiple,能夠被1到20所有數字整除的正整數裡,最小是多少。
首先是計算最大公因數與最小公倍數的函式。
def gcd(a, b):
while b:
a, b = b, a%b
return a
def lcm(a, b):
return a * b // gcd(a, b)
然後是題目本身,一次處理兩個數,不斷算出兩個數的最小公倍數,1跟2的最小公倍數是2,2跟3的最小公倍數是6,6跟4的最小公倍數是12,依此類推。底下函式傳入參數1與20,即可算出答案。
def sm(x, y):
m = 1
for n in range(x, y+1):
m = lcm(m, n)
return m
Problem 6: Sum square difference,前100個自然數(正整數)的平方和與和平方的差值。
呃,沒什麼好說的,數字小、計算量少,直接暴力法即可。底下函式傳入參數100可得到答案。
def ssd(n):
sum_sq = sum(i**2 for i in range(1, n+1))
sq_sum = sum(range(1, n+1)) ** 2
return sq_sum - sum_sq
Problem 7: 10001st prime,求第10001個質數。
底下函式可判斷參數n是否為質數,檢查小於n的數之中,是否有可以整除n的數存在,但不需要檢查「小於n」的數,只需檢查「小於n開根號+1」的數即可。
def is_prime(n):
if n % 2 == 0:
return False
p = 3
n_sqrt = n**0.5 + 1
while p < n_sqrt:
if n % p == 0:
return False
p += 2
return True
然後是問題本身,從3開始,逐一判斷下一個(+2)是否為質數,直到目標。底下函式傳入參數10001便可算出答案。
def nth_prime(n):
prime = 2
count = 1
p_next = 3
while count < n:
if is_prime(p_next):
prime = p_next
count += 1
p_next += 2
return prime
Problem 8: Largest product in a series,給定一個有100位數的數字,找出其中相鄰的13個位數、位數的乘積最大。
暴力法,逐一算出乘積,比較哪個大。
def lpias(num, n):
num_str = str(num)
num_len = len(num_str)
def prod(ns):
p = 1
for i in ns:
p *= int(i)
return p
max = 1
for i in range(0, num_len - n + 1):
m = prod(num_str[i:i+n])
if m > max:
max = m
return max
Problem 9: Special Pythagorean triplet,只有一組畢氏三元數組a、b、c能使得a+b+c等於1000,請算出a*b*c。
首先,判斷a、b、c是否為畢氏三元數組。
def is_pythagorean_triplet(a, b, c):
return a**2 + b**2 == c**2
然後,底下產生器函式可產生出a + b + c = n而且a < b < c的三數組。注意,其中range的參數並非最佳化。
def abc_gf(n):
for c in range(n//3, n):
for b in range((n-c)//2, n-c):
a = n - c - b
if a < b < c:
yield a, b, c
最後是問題本身,底下函式傳入參數1000,即可找出答案。
def spr(n):
for a, b, c in abc_gf(n):
if is_pythagorean_triplet(a, b, c):
return a*b*c
Problem 10: Summation of primes,找出小於兩百萬的所有質數,加總求和。
使用埃拉托斯特尼篩法找出小於n的質數。
def prime_sieve(n):
primes = set(range(2, n+1))
for i in range(2, (n+1+1) // 2):
if i in primes:
m = 2
while i*m <= n:
primes.discard(i*m)
m += 1
return primes
然後加總即可。底下函式傳入參數2000000即可算出答案。
def sop(n):
return sum(prime_sieve(n))
參考資料:
- Project Euler Solutions - Dreamshire,相當不錯,說明簡短精要。
- Project Euler -- Python,只有程式碼。
- Project Euler Solutions - Zach Denton,提供多種語言的解答程式碼,部分提供分析與說明。
- Project Euler: Python solutions,目標改成在10秒內算出答案。
- GitHub tokland/pyeuler,以純函數式程式設計的方式來解題。
No comments:
Post a Comment