數(shù)論入門：如何快速求出與n互素的數(shù)

01 故事起源

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

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

02 分析

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

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

03 歐拉函數(shù)

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

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

3.1 性質(zhì)1

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

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

3. 性質(zhì)2

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

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

04 計算

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

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

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