歐拉函數的定義:E(k)=([1,n-1]中與n互質的整數個數).
???
???? 由于隨意正整數都能夠唯一表示成例如以下形式:
???????????????????? k=p1^a1*p2^a2*……*pi^ai;(即分解質因數形式)
??? 能夠推出:E(k)=(p1-1)(p2-1)……(pi-1)*(p1^(a1-1))(p2^(a2-1))……(pi^(ai-1))
?????????????? =k*(p1-1)(p2-1)……(pi-1)/(p1*p2*……pi);
?????????????? =k*(1-1/p1)*(1-1/p2)....(1-1/pk)
???? ps:在程序中利用歐拉函數例如以下性質,能夠高速求出歐拉函數的值(a為N的質因素)
若(N%a==0 && (N/a)%a==0) 則有:E(N)=E(N/a)*a;
若(N%a==0 && (N/a)%a!=0) 則有:E(N)=E(N/a)*(a-1);
http://hi.baidu.com/ldante/blog/item/996b0ea131a7a58f46106443.html
第一次寫歐拉函數的題,琢磨的半天,最后還是僅僅能依照最開始的想法寫......
歐拉函數PHI(n)表示的是比n小,而且與n互質的正整數的個數(包含1)。比方:
PHI(1) = 1; PHI(2) = 1; PHI(3) = 2; PHI(4) = 2; ... PHI(9) = 6; ...
要計算一個正整數n的歐拉函數的方法例如以下:
1. 將n表示成素數的乘積: n = p1 ^ k1 * p2 ^ k2 * ... * pn ^ kn(這里p1, p2, ..., pn是素數)
2. PHI(n) =
(p1 ^ k1 - p1 ^ (k1 - 1))
*
(p2 ^ k2 - p2 ^ (k2 - 1))
* ... *
(pn ^ kn - pn ^ (kn - 1))
????????????? = Mult { pi ^ ki - pi ^ (ki -1) }
證明步驟例如以下:
1. easy想到:當n為素數時,PHI(n) = n - 1。由于每一個比n小的正整數都和n互素。當n為素數p的k次方時,PHI(n) = p ^ k - p ^ (k - 1)。由于在1到n之間的正整數僅僅有p的倍數和n不互素,這種數有(p ^ k / p)個。
2. 假設m和n互素,即GCD(m, n) = 1,那么PHI(m * n) = PHI(m) * PHI(n)。用中國剩余定理能夠證明,證明的思路是建立這樣一種一一相應的關系(a, b) <-> x,當中正整數a小于m而且gcd(a, m) = 1,正整數b小于n而且gcd(b, n) = 1,正整數x小于m*n而且gcd(m*n, x) = 1。證明步驟例如以下:
??? 1)依據中國剩余定理,假設m和n互素,那么關于未知量x的方程組x % m = a, x % n = b(0 <= a < m, 0 <= b < n),當0 <= x < m * n時存在而且僅存在一個解。easy證明,假設兩個這種方程組有同樣的m, n可是a, b不同,那么他們的解x一定不同。
??? 2)首先用反正法證明:gcd(m, a) = 1且gcd(n, b) = 1是gcd(m*n, x) = 1的必要條件:如果gcd(a, m) = k > 1,由此可得:a = a' * k; m = m' * k => x = k' * m + a = k' * k * m' + k * a' = k * (k' * m' + a'); 所以gcd(x, m) = k > 1。同理可證,如果gcd(b, n) > 1, 那么gcd(x, n) > 1。所以x和m * n互素的必要條件是a和m互訴且b和n互素。
??? 3)接下來我們證明充分性:由x % m = a 能夠得到x = k * m + a;由歐幾里德算法求最大公約數的過程(就不證明了,呵呵,還得想)能夠知道gcd(x, m) = gcd(m, a) = 1;同理可得,假設gcd(n, b) = 1那么gcd(x, n) = 1。接下來非常easy得到:gcd(m*n, x) = 1。從而證明了充分性。
??? 4)上面三步的結論表明,數對(a, b)是能夠和x建立起一一相應的關系的,所以有多少個不同的(a, b),就有多少個不同的x。
3.將n分解成素數乘積后,顯然對于隨意的i, j(i != j)都滿足 pi ^ ki和pj ^ kj是互素的,于是能夠的到上面的公式。
跟據上面的公式,能夠得到關于歐拉函數的遞推關系:
如果素數p能整除n,那么
假設p還能整除n / p, PHI(n) = PHI(n / p) * p;
假設p不能整除n / p, PHI(n) = PHI(n / p) * (p - 1);
以下是兩種求歐拉函數的不同編程方法:
/*==================================================*\
|
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索:z360901061

微信掃一掃加我為好友
QQ號聯系: 360901061
您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點擊下面給點支持吧,站長非常感激您!手機微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點擊微信右上角掃一掃功能,選擇支付二維碼完成支付。
【本文對您有幫助就好】元
