多元選修課提到歐拉函數 $\phi$,想說蠻有趣的可以跟程式結合一下,看會發生什麼有趣的事情!
定義與公式
對於一個正整數 $n$,歐拉函數 $\phi(n)$ 表示閉區間 $[1,n]$ 中的正整數與 $n$ 互質的個數。定義序列 $p$ 為所有正整數 $n$ 質因數分解之後的數字。在不失一般性的假設序列 $p$ 的長度為 $r$,以質因數分解表示 $n$ 即為 $n = p_1^{k_1}\cdot p_2^{k_2}\cdots p_r^{k_r}$,則歐拉函數滿足以下關係式:
這次沒有報名APCS,因為報名手續有點麻煩,還要在學證明和教師簽名等等,所以就沒有報…。總之,利用ZeroJudge的測資來寫寫看,但在ZJ上面會過不能保證真的去考APCS的測資就一定會過!