01 故事起源

一個(gè)數(shù)n，在小于等于n的正整數(shù)[1,n]中，與n互素的數(shù)有多少個(gè)呢？

(注：x與n互素，說明x與n的最大公約數(shù)為1)

02 分析

最直觀的方法當(dāng)然就是直接枚舉所有小于n的數(shù)，再通過求最大公約數(shù)判斷即可。

但當(dāng)n很大的時(shí)候，這個(gè)方法就不優(yōu)了。可能有同學(xué)已經(jīng)發(fā)現(xiàn)了，這個(gè)不就是歐拉函數(shù)的定義嗎，所以今天我們從數(shù)學(xué)上來分析如何快速求解。

03 歐拉函數(shù)

歐拉函數(shù)定義如下：

歐拉函數(shù)具有幾個(gè)優(yōu)秀的性質(zhì)，先介紹幾個(gè)常用的數(shù)學(xué)符號(hào)，便于描述。

3.1 性質(zhì)1

當(dāng)n為素?cái)?shù)時(shí)，很明顯phi(n)=n-1，因?yàn)樗行∮趎的數(shù)都與n互素。

當(dāng)n為某個(gè)素?cái)?shù)p的冪次時(shí)，即n=p^k，則與n不互素的一定為p的倍數(shù)。 [1,n]中p的倍數(shù)一共有p^(k-1)個(gè)，所以互素的即為總數(shù)減去不互素的個(gè)數(shù)。

3. 性質(zhì)2

歐拉函數(shù)是一個(gè)積性函數(shù)，當(dāng)整數(shù)m,n互素時(shí)，phi(mn)=phi(m)*phi(n)。

這個(gè)性質(zhì)的證明需要用到同余和集合相關(guān)的定理，有點(diǎn)復(fù)雜，以后寫同余相關(guān)的知識(shí)再專門分享如何證明，現(xiàn)在就先記住這個(gè)性質(zhì)就行了。

04 計(jì)算

有了這2個(gè)性質(zhì)就可以推導(dǎo)出歐拉乘積公式。

接下來就只需要考慮如何對(duì)n進(jìn)行質(zhì)因素分解。 最簡單的方式可以直接枚舉，先找到最小的質(zhì)因子p1，然后除去所有p1因子，再對(duì)剩余的數(shù)繼續(xù)分解。

05 代碼實(shí)現(xiàn)