ProjectEuler 完成兩百題後的數學分享

Link: http://projecteuler.net/

如何開始？

很難說。如果沒有頭緒就從解答人數最多的題目開始。

以前面幾題來說，數學基本知識就是：

• 因數、倍數、整數分解
• 質數
• Fibonacci numbers

因數、倍數、整數分解

• 最大公因數、最小公倍數
• 因數個數

關於最大公因數求法，最經典的就是輾轉相除法 (Euclidean algorithm)。輾轉相除法還有其他應用，例如 Extended Euclidean algorithm，這可以解同餘方程式、中國餘式定理。

((前面多用簡單演算法，後面轉化問題後可能需要計算中國餘式定理))

關於因數個數，最經典的就是 divisor function，這類計算都需要質因數分解，下面會講怎麼找質數。另外求 Euler's totient function 也是很經典的算法。

質數

求區間內的質數：Sieve of Eratosthenes

這是很經典的演算法，很多題目都靠他。例如質數判定，確定 N 是不是質數，我們只要把不大於 sqrt(N) 的質數用篩法篩出來，接下來就可以試除法去確定。

ProjectEuler 題目設計不可能一招可以吃全部。

• 如果 N 不大我們甚至可以從 1 篩到 N
• 如果 Sqrt(N) 不大，從 1 篩到 Sqrt(N)
• 如果 N 有點大，我們可以從 1 篩到 M，M+1 篩到 2M，...，kM + 1 篩到 kM = N

最後面的是進階篩法，這種篩法也有應用空間。

關於篩法也可以用來找質數相關的東西，例如 divisor function，或是你能想到的好應用。發揮一下想像力。

另一個是機率性的質數判定，帶有誤差性質在理面的演算法。稍微提示一下：Java BigInteger 的質數判定的演算法。關於解題我會盡量使用 programming language 裡頭就內建好的功能。

Fibonacci numbers

題目不多但考起來還是要人命。

最基礎的算法就是一個一個算下去 ((依定義))，如果是計算特定 Fibonacci number，可以使用 Q-matrix 將時間複雜度 O(n) 降到 O(log(n))。另個層面是模運算，模運算只要碰到加減乘就不算太困難。

發揮想像力，ProjectEuler 不單只是問基本的 Fibonacci numbers，他還會問複雜有趣的遞迴關係數列，tribonacci numbers。

延伸的問題就是看數列，請你找遞迴關係，這也是很好的解題方向。