張本群

（興義民族師范學(xué)院，興義562400）

0 引言

問題的描述：求n 的歐拉函數(shù)，即為小于n 且與n互質(zhì)的數(shù)的個(gè)數(shù)（包含1）。下面均用Euler（n）來表示n 的歐拉函數(shù)。

對(duì)于歐拉函數(shù)的求解，一種方法是直接講最優(yōu)算法；另一種方法是通過概念的描述，找出問題的本質(zhì)，最后才寫出最優(yōu)算法。解決同一問題，用這兩種不同的方法，在實(shí)踐中對(duì)學(xué)生的接受程度和取得的效果進(jìn)行分析比較。

1 直接講解最優(yōu)算法

在往屆的授課時(shí)，講歐拉函數(shù)的求解時(shí)都是直接講最優(yōu)化的方法，利用歐拉函數(shù)的性質(zhì)：

對(duì)于一個(gè)正整數(shù)n 的素?cái)?shù)冪分解n=p1q1×p2q2×p3q3×…×pkqk

主要是求每一個(gè)素?cái)?shù)因子p1，p2，…，pk，根據(jù)上面的公式，就可求出歐拉函數(shù)。

時(shí)間復(fù)雜度為ο(sqrt(n))。具體算法如下：

但用這種方法學(xué)生不易理解，計(jì)算公式和問題的描述相差甚遠(yuǎn)，學(xué)生是知其然不知其所以然。對(duì)于怎么來的歐拉函數(shù)的性質(zhì)不理解，給出性質(zhì)后，能寫出算法，但如果不給性質(zhì)，學(xué)生是寫不出算法的，算法沒有寫出來，也就談不上對(duì)算法的分析了。于是，在教學(xué)過各中調(diào)整了教學(xué)內(nèi)容和方法，在這一學(xué)期的《算法分析與設(shè)計(jì)》中，先讓學(xué)生理解問題的描述，分析問題的本質(zhì)，最后再著手寫最優(yōu)的算法。

2 改進(jìn)后的教學(xué)內(nèi)容及方法

2.1 先理解概念

先根據(jù)問題的描述，理解概念，即直接用概念來解決問題（蠻力法）。

求n 的歐拉函數(shù)，就是小于n 且與n 互質(zhì)的數(shù)的個(gè)數(shù)（包含1）。那么，賦歐拉函數(shù)初始值為1，對(duì)于小于n 的數(shù)i（i 從2 到n-1），逐個(gè)判定i 與n 有沒有除1以外的其他因數(shù)，如果有，判定下一個(gè)，否則歐拉函數(shù)加1。

算法對(duì)小于n 的數(shù)i（i 從2 到n-1），判定i 與n 有沒有除1 以外的其他因數(shù)，如果有，跳過這個(gè)數(shù)，如果沒有，即i 與n 互質(zhì)，與n 互質(zhì)的數(shù)加1。最后函的的返回什就是歐拉函數(shù)的值。這樣寫學(xué)生很容易理解，完全根據(jù)概念來寫算法，但該算法有很多重復(fù)的計(jì)算。例如，求Euler（10），已經(jīng)判定2 是10 的因數(shù)了，那么只要是含有因數(shù)2 的數(shù)，都不會(huì)和10 互質(zhì)。我們?cè)倥卸?，6，8 是否為10 的因數(shù)，就顯然是重復(fù)的計(jì)算，該算法的時(shí)間復(fù)雜度為O(n2)。明顯有改進(jìn)的空間。為了避免如此重復(fù)的計(jì)算，想到用類似于篩法求素?cái)?shù)的方法，用篩法刪去與n 不是互質(zhì)的數(shù)，剩下的就是與n 互質(zhì)的數(shù)了。

2.2 分析問題的本質(zhì)

根據(jù)問題的描述，分析出歐拉函數(shù)Euler（n）本質(zhì)特征。

如果n 是素?cái)?shù)，根據(jù)素?cái)?shù)的概念，n 沒有除1 和它本身以外的其他因數(shù)，n 與i（i 從1 到n-1）都是互質(zhì)的，由此得出性質(zhì)1。

性質(zhì)1：如果n 是素?cái)?shù)，Euler（n）=n-1；

事實(shí)上，對(duì)于兩個(gè)不同的素?cái)?shù)p 和q，有Euler（pq）=Euler（p）×Euler（q）

對(duì)于1 到pq 間的數(shù)，因?yàn)閜，q 不相同的素?cái)?shù)，它們間的共同因數(shù)p 的倍數(shù)和q 的倍數(shù)，即p，2p，…，（q-1）p，qp 和q，2q，…，（p-1）q，pq。又因?yàn)閜q 既是p 的倍數(shù)，又是q 的倍數(shù)，所以Euler（pq）=pq-p-q+1=（p-1）（q-1）=Euler（p）×Euler（q）

推廣得出，對(duì)任意兩個(gè)互為質(zhì)數(shù)的m，n；均有Euler（mn）=Euler（n）×Euler（m）

證明：由m，n 均為素?cái)?shù)可知m，n 無公因數(shù)，得出：

Euler（m）Euler（n）=m（1-1/p1）（1-1/p2）（1-1/p3）…（1-1/pk）·n（1-1/q1）（1-1/q2）（1-1/q3）…（1-1/qr），其中p1，p2，p3，…，pk 為m 的質(zhì)因數(shù)，q1，q2，q3，…，qr 為n 的質(zhì)因數(shù)，而m，n 無公因數(shù)，所以p1，p2，p3，…，pk，q1，q2，q3，…，qr 互不相同，所以p1，p2，p3，…，pk，q1，q2，q3，…，qr 均為mn 的質(zhì)因數(shù)且為mn質(zhì)因數(shù)的全集，所以Euler（mn）=mn（1-1/p1）（1-1/p2）（1-1/p3）…（1-1/pk）（1-1/q1）（1-1/q2）（1-1/q3）…（1-1/qr），所以Euler（mn）=Euler（m）Euler（n）。

即Euler（mn）=Euler（n）×Euler（m）

如果n 有一個(gè)素?cái)?shù)因數(shù)p1，那么p1 的所有倍數(shù)將被岀除，也就是p1 的所有倍數(shù)都不會(huì)與n 互質(zhì)，由此可推得下面的性質(zhì)。

性質(zhì)2：對(duì)于一個(gè)正整數(shù)n 的素?cái)?shù)冪分解n=p1q1×p2q2×p3q3×…×pkqk

根據(jù)性質(zhì)2，刪除掉所有素?cái)?shù)因數(shù)p1，p2，…，pk 的倍數(shù)，所剩的數(shù)的個(gè)數(shù)就是歐拉函數(shù)。類似于用篩法求素?cái)?shù)的方法，用篩法求與n 互質(zhì)的數(shù)。具體程序如下：

算法的時(shí)間復(fù)雜度為ο(nsqrt(n))。這一算法相對(duì)于根據(jù)概念逐個(gè)判定的方法有所改進(jìn)，但仍然有可以再改進(jìn)的地方。對(duì)于n 的每一個(gè)素?cái)?shù)因數(shù)，我們都要遍歷一次它的倍數(shù)，把該數(shù)換成0，篩選結(jié)束后又要遍歷小于n 的每一個(gè)數(shù)組元素，不為0時(shí)才計(jì)數(shù)。

2.3 分析寫出最優(yōu)算法

事實(shí)上，求n 的歐拉函數(shù)只是求與n 與小于n 且與n 互質(zhì)的個(gè)數(shù)，并沒有要求求出哪些數(shù)與它互質(zhì)，所以當(dāng)找出n 的一個(gè)素?cái)?shù)因數(shù)p 時(shí)，只需找出包含有因數(shù)p1 的數(shù)的個(gè)數(shù)即可，如果p1 是n 的一個(gè)素?cái)?shù)因數(shù)，則有個(gè)n/p1 個(gè)數(shù)與n 有共同因數(shù)，故除去p1 的倍數(shù)后，還剩n-n/p1 個(gè)，以此類推，對(duì)于n 的全部互不相同的素?cái)?shù)因數(shù)p1，p2，…，pk，歐拉函數(shù)

此算法在找出素?cái)?shù)因數(shù)的同時(shí)就求出了歐拉函數(shù)。如72 的素?cái)?shù)因數(shù)為2 和3，euler（72）=72×（1-1/2）（1-1/3）=24，最差的情況就是n 為素?cái)?shù)時(shí)，需要搜索時(shí)間為ο(sqrt(n))。此算法的關(guān)鍵在于計(jì)算res=res/i*（i-1）時(shí)刪除了i 的所有倍數(shù)，while（a%i==0）a/=i;展轉(zhuǎn)相除后所得的a 不會(huì)包含因數(shù)i。

3 比較結(jié)果

對(duì)于n 的全部互不相同的素?cái)?shù)因數(shù)p1，p2，…，pk，歐拉函數(shù)

這一描述中強(qiáng)調(diào)了三個(gè)問題，第一是全部，即不能是一部份，因數(shù)從2 到n 本身；第二是素?cái)?shù)因數(shù)，如72＝8×9，不能用來求euler（72），原因是8 和9 雖然是72 的因數(shù)，但它們不是素?cái)?shù)，故euler（72）＝72（1-1/8）（1-9）＝56 是錯(cuò)的，是素?cái)?shù)不是因數(shù)也不行，例如5 是素?cái)?shù)，但5 不是72 的因數(shù)，因此也不能算；第三是互不相同，如72=2×2×2×3×3，有3 個(gè)因數(shù)是2，2 個(gè)因數(shù)3，2和3 均為素?cái)?shù)，但2 和3 都只能算一次，而不能算多次，所以在找到一個(gè)素?cái)?shù)因數(shù)p 時(shí)，不是進(jìn)行下一輪的循環(huán)，急于找下一個(gè)因數(shù)，而是輾轉(zhuǎn)除去所有的因數(shù)p，得到的新數(shù)n 繼續(xù)找素?cái)?shù)因數(shù)。

如果直接根據(jù)性質(zhì)2 來講解，學(xué)生不易理解。通過概念，直接用蠻力求n 的歐拉函數(shù)，時(shí)間復(fù)雜度是ο(n2)，用篩法先將互質(zhì)因數(shù)篩出來，再線性搜索出不為0 的結(jié)果，時(shí)間復(fù)雜度為ο(nsqrt(n))，而用改進(jìn)后用篩法，找出素?cái)?shù)因數(shù)的同時(shí)就再接算歐拉函數(shù)，同時(shí)除去所有含該因數(shù)的數(shù)，時(shí)間復(fù)雜度是ο(sqrt(n))；時(shí)間上得到了很大的提高，所以對(duì)同一個(gè)問題的求解，由于使用的算法不同，花費(fèi)的時(shí)間完成不一樣。顯然，改進(jìn)后的算法更有效。通過這一問題的講解，讓學(xué)生認(rèn)識(shí)到解決問題前要先分析，找出問題的本質(zhì)特征，再著手分析寫出算法，寫出更好的算法。這樣逐步優(yōu)化時(shí)間復(fù)雜度的教學(xué)方法，使學(xué)生體會(huì)到對(duì)算法分析的重要性，學(xué)生效果更好。