歐拉函數演算法

㈠ 計算歐拉函數φ(100),寫出詳細過程

得知

φ(100)=φ(25*4)=φ(25)φ(4)=φ(5^2)φ(2^2)=5φ(5)*2φ(2)=5(5-1)*2(2-1)=40

㈡ 歐拉函數計算公式的推導（要詳細過程）

性質① m是素數時，有φ(m)=m-1
性質② 當m、n互素時，φ(m*n)=φ(m)*φ(n)
性質③ 對一切正整數n，有φ(p^n)=[p^(n-1)]*(p-1)

㈢ 歐拉函數 Pascal （用線性篩法）

下面的代碼用的是線性篩法求素數，然後再求GCD的方法。

programEulerPhi;
type
AList=arrayofWord;
procereaddtolist(vararr:AList;num:Word);
var
size:Word;
begin
size:=Length(arr);
setlength(arr,size+1);
arr[size]:=num;
end;

functionprime_decomp(num:Word):AList;
var
result:AList;
i:Word;
begin
result:=nil;
while((nummod2)=0)do
begin
addtolist(result,2);
num:=numdiv2;
end;

i:=3;
while(i*i<=num)do
begin
while((nummodi)=0)do
begin
addtolist(result,i);
num:=numdivi;
end;
i:=i+2;
end;
ifnum>2thenaddtolist(result,num);
prime_decomp:=result;
end;
functiongcd_check(constnum:Word;varlist:AList):boolean;
var
i:Word;
begin
fori:=low(list)tohigh(list)do
if(nummodlist[i])=0thenexit(false);
exit(true);
end;
var
instr:String;
i,num,errcode,phi:integer;
decomp:AList;
begin
writeln('Inputapositiveinteger:');
readln(instr);

repeat
Val(instr,num,errcode);
iferrcode=0thenbreak;
writeln('errorinput,tryagagin.');
until1=0;

decomp:=prime_decomp(num);
phi:=1;
fori:=2tonumdo
ifgcd_check(i,decomp)theninc(phi);

writeln('Euler''stotient=',phi);
end.

運行結果：

Inputapositiveinteger:
128
Euler'stotient=64

㈣ 請問有什麼演算法可以「根據兩個素數的乘積和這兩個素數的歐拉函數，快速地求解得到這兩個素數」謝謝！

一個素數p的歐拉函數的值是p-1,因為歐拉函數的定義就是比這個數字小的所有數字中,與他互素的個數比他小的有p-1個,而且p是素數,不可能有除1以外的因子了,而比p小的數又不可能是p的倍數,所以就都和他互質.
你給兩個素數的歐拉函數 值嗎？只要給一個就行了啊
p*q=n
p的歐拉值為m
那麼p=m+1
q=n/(m+1)

㈤ 演算法里的MOD是什麼意思，怎麼運算

意思就是取模，就是取余數。運算方法：比如10mod3，余數是1，結果就是1。

㈥ 求歐拉函數的計算公式

歐拉函數From KeyinWikiJump to: navigation, search在數論，對正整數n，歐拉函數\varphi(n)是少於或等於n的數中與n互質的數的數目。此函數以其首名研究者歐拉命名，它又稱為Euler's totient function、φ函數、歐拉商數等。 例如\varphi(8)=4，因為1,3,5,7均和8互質。 從歐拉函數引伸出來在環論方面的事實和拉格朗日定理構成了歐拉定理的證明。 [編輯]φ函數的值\varphi(1)=1（唯一和1互質的數就是1本身）。 若n是質數p的k次冪，\varphi(n)=p^a-p^{a-1}=(p-1)p^{k-1}，因為除了p的倍數外，其他數都跟n互質。 歐拉函數是積性函數——若m,n互質，\varphi(mn)=\varphi(m)\varphi(n)。證明：設A, B, C是跟m, n, mn互質的數的集，據中國剩餘定理，A \times B和C可建立一一對應的關系。因此\varphi(n)的值使用算術基本定理便知， 若n = \prod_{p\mid n} p^{\alpha_p}， 則\varphi(n) = \prod_{p\mid n} p^{\alpha_p-1}(p-1) = n\prod_{p|n}\left(1-\frac{1}{p}\right)。 例如\varphi(72)=\varphi(2^3\times3^2)=2^{3-1}(2-1)\times3^{2-1}(3-1)=2^2\times1\times3\times2=24 [編輯]和費馬小定理的關系對任何兩個互質的正整數a, m，m\ge2，有 a^{\varphi(m)} \equiv 1 \pmod m 當m是質數p時，此式則為： a^{p-1} \equiv 1 \pmod p 即費馬小定理。de:Eulersche φ-Funktion en:Euler's totient function es:Función fi de Euler fr:Indicatrice d'Euler hu:Euler-függvény it:Funzione phi di Eulero ja:オイラーのφ関數 ko: nl:Indicator van n sl:Eulerjeva funkcija fi sv:Eulers phi-funktion 取自" http://wiki.keyin.cn/index.php/%E6%AC%A7%E6%8B%89%E5%87%BD%E6%95%B0"

㈦ C語言算一個數歐拉函數，輸入0結束

unsigned int ss(unsigned int a)
{
unsigned int i;
for(i=2;i*i<=a;i++) {
if(a%i==0) break;
}
if(i*i<=a) return 0;
else return 1;
}
這個判斷素數的函數邏輯是：

i在2~根號a（a是外部傳入的需要判斷的正整數）之間循環遞增1，

如果a能被i整除，則跳出循環，否則繼續循環直至i大於根號a退出循環，

退出循環後，判斷當前i值是否小於根號a，

小於等於根號a，則是中途退出，返回0（是合數）；

大於根號a，則是循環條件完成退出，返回1（是質數）。

函數ss( a)在函數unsigned int oula(unsigned int n)中調用

unsigned int oula(unsigned int n)
{
unsigned int f=n,p;
for(p=2;p<=n;p++)
if(ss(p)&&(n%p==0)) f=f*(1-(1/p)); 調用處
return f;
}

輸入100,000,000，要看編譯器對unsigned int的定義，

如果編譯器定義為2 byte，則范圍是：0~2^16-1(62353)，此時100,000,000會溢出。

如果編譯器定義為4 byte，則范圍是：0~4294967295,大於100,000,000.此時可以輸入，但因數據太大，計算完成要超過2分鍾（用去年主流配置的x86電腦測試），輸入10,000,000就感覺明顯的時延，要約20秒才能輸出結果。

測試截圖如下圖：

另，函數unsigned int oula(unsigned int n)需要改成：

unsigned int oula(unsigned int n)
{
unsigned int f=n,p;
for(p=2;p<=n;p++)
if(ss(p)&&(n%p==0))
//f=f*(1-(1/p)); //修改小數部分丟失問題
f=f*(p-1)/p;
return f;
}

供參考。

㈧ 歐拉函數21怎麼算

歐拉函數21計算：

分解質因數：21=2^3*3*5。

歐拉函數：φ(21)=21*(1-1/2)(1-1/3)(1-1/5)=120*1/2*2/3*4/5=32。

小於或等於n的正整數中與n互質的數的數目（因此φ(1)=1）。設n為正整數，以 φ(n)表示不超過n且與n互素的正整數的個數，稱為n的歐拉函數值φ：N→N，n→φ(n)稱為歐拉函數。

函數的近代定義

是給定一個數集A，假設其中的元素為x，對A中的元素x施加對應法則f，記作f（x），得到另一數集B，假設B中的元素為y，則y與x之間的等量關系可以用y=f（x）表示，函數概念含有三個要素：定義域A、值域B和對應法則f。其中核心是對應法則f，它是函數關系的本質特徵。

㈨ 歐拉函數φ(120)怎麼算

分解質因數：120=2^3*3*5

歐拉函數：φ(120)=120*(1-1/2)(1-1/3)(1-1/5)=120*1/2*2/3*4/5=32

小於或等於n的正整數中與n互質的數的數目（因此φ(1)=1）。

設n為正整數，以 φ(n)表示不超過n且與n互素的正整數的個數，稱為n的歐拉函數值φ：N→N，n→φ(n)稱為歐拉函數。

(9)歐拉函數演算法擴展閱讀：

利用歐拉函數和它本身不同質因數的關系，用篩法計算出某個范圍內所有數的歐拉函數值。

如：

ψ（10）=10×（1－1/2）×（1－1/5）=4；

ψ（30）=30×（1－1/2）×（1－1/3）×（1－1/5）=8。

㈩ 計算20以內的正整數的歐拉函數值

phi(1)=1
phi(2)=1
phi(3)=2
phi(4)=2
phi(5)=4
phi(6)=2
phi(7)=6
phi(8)=4
phi(9)=6
phi(10)=4
phi(11)=10
phi(12)=4
phi(13)=12
phi(14)=6
phi(15)=8
phi(16)=8
phi(17)=16
phi(18)=6
phi(19)=18
phi(20)=8
具體計算規則將n素因子分解為(p1^a1)(p2^a2)...(pk^ak)
則phi(n)=n(1-1/p1)(1-1/p2).....(1-1/pk)
如n=18=2×3² 則phi(18)=18(1-1/2)(1-1/3)=18×1/2×2/3=9×2/3=6