简介

φ函数的值 通式：φ(x)=x(1-1/p1)(1-1/p2)(1-1/p3)(1-1/p4)…..(1-1/pn),其中p1, p2……pn为x的所有质因数，x是不为0的整数。φ(1)=1（唯一和1互质的数就是1本身）。 (注意：每种质因数只一个。比如12=2*2*3

欧拉公式

那么φ（12）=12*（1-1/2）*(1-1/3)=4)若n是质数p的k次幂，φ(n)=p^k-p^(k-1)=(p-1)p^(k-1)，因为除了p的倍数外，其他数都跟n互质。欧拉函数是积性函数——若m,n互质，φ(mn)=φ(m)φ(n)。特殊性质：当n为奇数时，φ(2n)=φ(n), 证明于上述类似。

证明

设A, B, C是跟m, n, mn互质的数的集，据中国剩余定理，A*B和C可建立一一对应的关系。因此φ(n)的值使用算术基本定理便知，若n=∏p^(α（下标p）)p|n则φ(n)=∏(p-1)p^(α（下标p）-1)=n∏(1-1/p)p|n p|n例如φ(72)=φ(2^3×3^2)=(2-1)2^(3-1)×(3-1)3^(2-1)=24与欧拉定理、费马小定理的关系对任何两个互质的正整数a, m, m>=2有a^φ(m)≡1(mod m)即欧拉定理当m是质数p时，此式则为：a^(p-1)≡1(mod m)即费马小定理。

欧拉函数的编程实现

利用欧拉函数和它本身不同质因数的关系，用筛法计算出某个范围内所有数的欧拉函数值。欧拉函数和它本身不同质因数的关系：欧拉函数ψ（N）=N{∏p|N}（1－1/p）。（P是数N的质因数）如：ψ（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）=42。#include#define N 10000000main(){int *phi,i,j;char *prime;prime=(char*)malloc((N+1)*sizeof(char));prime[0]=prime[1]=0;for(i=2;i<=N;i++){prime[i]=1;}for(i=2;i*i<=N;i++){if(prime[i]){for(j=i*i;j<=N;j+=i){prime[j]=0;}}} //这段求出了N内的所有素数phi=(int*)malloc((N+1)*sizeof(int));for(i=1;i<=N;i++){phi[i]=i;}for(i=2;i<=N;i++){if(prime[i]){for(j=i;j<=N;j+=i){phi[j]=phi[j]/i*(i-1); //此处注意先/i再*（i-1)，否则范围较大时会溢出}}//这段求出了N内所有数的欧拉函数值2-100欧拉函数表n φ(n)2 13 24 25 46 27 68 49 610 411 1012 413 1214 615 816 817 1618 619 1820 821 1222 1023 2224 825 2026 1227 1828 1229 2830 831 3032 1633 2034 1635 2436 1237 3638 1839 2440 1641 4042 1243 4244 2045 2446 2247 4648 1649 4250 2051 3252 2453 5254 1855 4056 2457 3658 2859 5860 1661 6062 3063 3664 3265 4866 2067 6668 3269 4470 2471 7072 2473 7274 3675 4076 3677 6078 2479 7880 3281 5482 4083 8284 2485 6486 4287 5688 4089 8890 2491 7292 4493 6094 4695 7296 3297 9698 4299 60100 40pascal版写的，贴一下：constmaxn=10000;sqrtn=trunc(sqrt(maxn));vari,j,n,si:longint;fi:array[1..maxn] of longint;hash:array[1..sqrtn] of boolean;ssb:array[1..sqrtn] of longint;procedure yuchuli;vari,j,daili:longint; pd:boolean;beginfillchar(hash,sizeof(hash),false);i:=2; si:=0;while i<=sqrtn dobeginif not hash[i] thenbeginfor j:=i+1 to sqrtn div i dohash[i*j]:=true;inc(si);ssb[si]:=i;end;inc(i);end;for i:=1 to maxn do fi[i]:=1;for i:=2 to maxn dobegindaili:=i;for j:=1 to si dobeginpd:=false;while daili mod ssb[j]=0 dobegindaili:=daili div ssb[j];if not pd thenfi[i]:=fi[i]*(ssb[j]-1) else fi[i]:=fi[i]*(ssb[j]);pd:=true;end;end;if daili1 then fi[i]:=fi[i]*(daili-1);end;end;beginyuchuli;readln(n);writeln(fi[n]);readln;end.C语言：int eular(int n){int ret=1,i;for(i=2;i*i1)ret*=n-1;return ret;}