相信有一部分同學以前聽說過歐拉函數吧，雖然定義聽上去簡單，但實際的應用比較廣泛。今天我就來介紹一下歐拉函數，漲漲知識！
歐拉真是個偉大的數學家（物理、天文……），到處都掛著他的名字，包括我寫過的往期文章哦：
一筆畫問題——歐拉迴路與 Fleury算法
無憂公主
我們定義 φ(n) 為 1~n 的正整數中，與 n 互質的數的個數（不包括 n 本身，φ(1)=1 為特殊情況），注意這個符號讀作 fai。可能在小學裡我們就學過了這個個數的求法，設 n 的所有質因數為 p1，p2，……，pk，則：
φ(n) = n × ( 1 - 1/p1 ) × ( 1 - 1/p2 ) × …… × ( 1 - 1/pk )
這個其實比較好理解吧，與質數 p1 不互質的數只可能是 p1 的倍數，因此在前 n 個正整數中，與 p1 互質的數在每 p1 個中有 ( p1 - 1 ) 個，倍數在每 p1 個中只有 1 個。由此可以得出上述算式。
這裡我介紹歐拉函數幾個重要的性質，大家可以自己思考理解一下。
若 n 是奇數，則 φ(2n) = φ(n)；
若 n 是質數，則 φ(n) = n-1；
若 a 與 b 互質，則 φ(ab)=φ(a)×φ(b)，即歐拉函數為積性函數；
若 n = p^k，p 為質數，則 φ(n) = n - p^(k-1) = ( p - 1 ) × p^(k-1)，即 n - p 的倍數的個數；
之前都是數學推導，如果需要編程求出 φ(n) 該怎麼辦呢？如果將 n 分解質因數，可能會比較慢。接下來介紹一種通過線性遞推來計算的方法，但具體證明方法不是很複雜，這裡就不細說了，可以利用歐拉函數的性質等來證明。
設 p 為 n 的最小質因數，若 p^2 | n，則 φ(n) = φ( n/p ) × p；反之，φ(n) = φ( n/p ) × ( p - 1 )，相當於積性函數的性質。
用這樣的遞推方法，時間複雜度就降到了 O ( n )，外帶的福利是求出了 φ(1) ~ φ(n) 的所有值。
今天介紹的歐拉函數就到這裡為止了，但歐拉函數真正的性質和用處還遠沒有 「 為止 」。接下來我想介紹歐拉定理，和歐拉函數有關，感興趣的同學可以提前預習一下哦。
最後講一個小八卦吧，其實歐拉剛發明歐拉函數時，並沒有 φ 這個符號。當時他也沒有想好用什麼符號，別人使用時也有改動，並沒有統一。在歐拉去世的二十年後，高斯提出了 φ 這個希臘字母，不過是不帶括號的。又過了幾十年，人們覺得還是不夠清楚，所以加上了括號，沿用至今。
這是我自己學習的筆記，大家如果有什麼異議、問題或者建議，歡迎留言。