欧拉函式

函式内容

其中p1, p2……pn为x的所有质因数，x是不为0的整数。

φ(1)=1（和1互质的数(小于等于1)就是1本身）。

注意：每种质因数只一个。 比如12=2*2*3那么φ（12）=φ（4*3）=φ（2^2*3^1）=（2^2-2^1）*（3^1-3^0）=4

若n是质数p的k次幂，

设n为正整数，以 φ(n)表示不超过n且与n互素的正整数的个数，称为n的欧拉函式值

φ：N→N，n→φ(n)称为欧拉函式。

欧拉函式是积性函式——若m,n互质，

特殊性质：当n为奇质数时，

若n为质数则

证明

设A, B, C是跟m, n, mn互质的数的集，据中国剩余定理，A*B和C可建立一一对应的关係。因此φ(n)的值使用算术基本定理便知，

若

则

例如

与欧拉定理、费马小定理的关係

对任何两个互质的正整数a, m(m>=2)有

即欧拉定理

当m是质数p时，此式则为：

即费马小定理。

编程实现

利用欧拉函式和它本身不同质因数的关係，用筛法计算出某个範围内所有数的欧拉函式值。

欧拉函式和它本身不同质因数的关係：

欧拉函式ψ（N）=N{∏p|N}（1－1/p）

亦即:

如：

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

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

ψ（49）=49×（1－1/7）=

C++版

/*特性:1.若a为质数,phi[a]=a-1;2.若a为质数,bmoda=0,phi[a*b]=phi[b]*a3.若a,b互质,phi[a*b]=phi[a]*phi[b](当a为质数时,ifbmoda!=0,phi[a*b]=phi[a]*phi[b])*/intm[n],phi[n],p[n],nump;//m[i]标记i是否为素数,0为素数,1不为素数;p是存放素数的数组;nump是当前素数个数;phi[i]为欧拉函式intmain(){phi[1]=1;for(inti=2;i<=n;i++){if(!m[i])//i为素数{p[++nump]=i;//将i加入素数数组p中phi[i]=i-1;//因为i是素数,由特性得知}for(intj=1;j<=nump&&p[j]*i<=n;j++)//用当前已得到的素数数组p筛,筛去p[j]*i{m[p[j]*i]=1;//可以确定i*p[j]不是素数if(i%p[j]==0)//看p[j]是否是i的约数,因为素数p[j],等于判断i和p[j]是否互质{phi[p[j]*i]=phi[i]*p[j];//特性2break;}elsephi[p[j]*i]=phi[i]*(p[j]-1);//互质,特性3其,p[j]-1就是phi[p[j]]}}}

pascal版

constmaxn=10000;sqrtn=trunc(sqrt(maxn));vari,j,n,si:longint;fi:array[1..maxn]oflongint;hash:array[1..sqrtn]ofboolean;ssb:array[1..sqrtn]oflongint;procedureyuchuli;vari,j,daili:longint;pd:boolean;beginfillchar(hash,sizeof(hash),false);i:=2;si:=0;whilei<=sqrt(maxn)dobeginifnothash[i]thenbeginforj:=i+1tosqrt(ndivi)dohash[i*j]:=true;inc(si);ssb[si]:=i;end;inc(i);end;fori:=1tomaxndofi[i]:=1;fori:=2tomaxndobegindaili:=i;forj:=1tosidobeginpd:=false;whiledailimodssb[j]=0dobegindaili:=dailidivssb[j];ifnotpdthenfi[i]:=fi[i]*(ssb[j]-1)elsefi[i]:=fi[i]*ssb[j];pd:=true;end;end;ifdaili<>1thenfi[i]:=fi[i]*(daili-1);end;end;beginyuchuli;readln(n);writeln(fi[n]);end.

C语言

#include#includeinteular(intn){intret=1,i;for(i=2;i*i<=n;i++){if(n%i==0){n/=i,ret*=i-1;while(n%i==0)n/=i,ret*=i;}}if(n>1)ret*=n-1;returnret;}intmain(){intn,s;scanf(%d,&n);s=eular(n);printf(%d,s);return0;}

Java语言

importjava.util.ArrayList;importjava.util.List;importjava.util.Scanner;publicclassOula{publicstaticvoidmain(String[]args){Scannerscanner=newScanner(System.in);intnum=scanner.nextInt();inta=num;doubleoulaAnwser=0;ArrayListoulaList=newArrayList();if(isPrime(num)){oulaAnwser=num-1;}else{ListallPrime=getAllPrime(num);for(inti:allPrime){inttem=num;num=repeatdivide(num,i);if(tem!=num){oulaList.add(i);}}oulaAnwser=a;for(intj:oulaList){oulaAnwser=oulaAnwser*(1-(double)1/j);}}System.out.println(欧拉函式的值为+Math.round(oulaAnwser));}publicstaticListgetAllPrime(intnum){ArrayListresult=newArrayList();for(inti=2;i
 
C#语言
usingSystem;usingSystem.Collections.Generic;publicclassProgram{publicstaticvoidMain(string[]args){Console.Write(输入一个整数：);longnum=long.Parse(Console.ReadLine());longa=num;doubleoulaAnwser=0;ListoulaList=newList();if(IsPrime(num)){oulaAnwser=num-1;}else{ListallPrime=GetAllPrime(num);foreach(longiinallPrime){longtem=num;num=Repeatdivide(num,i);if(tem!=num){oulaList.Add(i);}}oulaAnwser=a;foreach(longjinoulaList){oulaAnwser=oulaAnwser*(1-(double)1/j);}}Console.WriteLine(欧拉函式的值为+Math.Round(oulaAnwser));Console.ReadLine();}publicstaticListGetAllPrime(longnum){Listresult=newList();for(longi=2;i
 
函式表
0~100欧拉函式表（“x?”代表十位数，“x”代表个位数）
φ(n)
0
1
2
3
4
5
6
7
8
9
0?
0
1
1
2
2
4
2
6
4
6
1?
4
10
4
12
6
8
8
16
6
18
2?
8
12
10
22
8
20
12
18
12
28
3?
8
30
16
20
16
24
12
36
18
24
4?
16
40
12
42
20
24
22
46
16
42
5?
20
32
24
52
18
40
24
36
28
58
6?
16
60
30
36
32
48
20
66
32
44
7?
24
70
24
72
36
40
36
60
24
78
8?
32
54
40
82
24
64
42
56
40
88
9?
24
72
44
60
46
72
32
96
42
60
φ(100)=40