Project Euler與Python：Problem 1~10

Project Euler針對數學和程式愛好者，設計了一系列的問題，至今已有五百多道，供大家挑戰，每一題都要求應在1分鐘內計算出答案。

我使用硬體Raspberry Pi 2與軟體Raspbian，作為執行速度的依據。

十八世紀數學家Leonhard Euler。

根據目前的統計，解出25~49題的人數將近四萬（38392），而解出超過450題的人數僅有45。

各種賞心悅目的成就徽章。

可先上去看看有哪些題目，若想開始解題，先註冊個帳號，然後便可輸入答案。每道問題經過設計，都以某數字作為明確的答案，在題目頁面的欄位「Answer:」裡提交，便可檢查是否正確解題。

若答案正確，可進入該問題的論壇，看看別的語言的解法，觀看其他人的討論文章。當然啦，網路上也可找到他人公布分享的程式原始碼，但如果直接照抄就失去意義了。

接下來試試第1~10題吧，我將以Python語言來解題，原始碼放在GitHub（yehnan/project_euler_python），基本上我都是先採用暴力法，若運算量太大，無法在1分鐘內算出答案，才著手研究想出更快的演算法。當題目的數字很小時，隨便寫就能在1分鐘內算出答案，但是，也就只有幾題而已，大部分的題目都需要大量計算，可沒那麼好混。

注意：並不提供詳細的說明與分析。

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，以純函數式程式設計的方式來解題。