欧拉函数，又称为Euler‘s totient function，在程序编辑中有很大的用途，所以在此总结一下。

欧拉函数定义

　　少于或等于n的数中与n互质的数的数目。

欧拉函数求法

　　因为任意正整数都可以唯一表示成如下形式: 

　　　　n=p1^a1*p2^a2*……*pi^ai  

　　可以推出:Eular(n)=n*(1-1/p1)*(1-1/p2)....(1-1/pi)；

      因为对于每一个质因子，比如2，那么在小于n的数中，与n不互质的，与其公约数是2的倍数的占其1/2，所以乘上1/2就是剩下与n公约数不含2的，然后依次类推，对于每个n的约数，乘上(pi-1/pi)，最后的答案就是欧拉函数值了。

欧拉函数代码

　　欧拉函数在程序语言中，有两种求法，一种是按照定义求出单个的欧拉函数，一种是求出一定范围内所有的欧拉函数。

单个欧拉函数 》

int Eular(int n){    int ret=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;    return ret;}

　　也许对于这个程序一开始看会有些迷糊，为什么没有按照定义乘上用n乘上(pi-1/pi)呢？因为一开始ret是赋值为1而不是n，那么就省去了除法的部分，而直接乘上pi-1即可。

筛法求欧拉函数 》

 for(i=1;i<=maxn;i++) phi[i]=i; for(i=2;i<=maxn;i+=2) phi[i]/=2; for(i=3;i<=maxn;i+=2)if(phi[i]==i){     for(j=i;j<=maxn;j+=i)phi[j]=phi[j]/i*(i-1); }

　　对于筛法求素数，想必大家已经非常地熟悉，那么筛法求欧拉函数也是同样的原理，对于每个质因子pi，要乘上(pi-1/pi)，那么最后phi数组就是答案了。

欧拉函数的应用

HDU 1286 找新朋友 欧拉函数模板题

题目大意：求一个小于一个数与其互质的数的个数

题解：欧拉函数的定义，直接应用。

#include <cstdio>int eular(int n){    int ret=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;    return ret;}int main(){    int n;    scanf("%d",&n);    while (scanf("%d",&n)!=EOF) printf("%d\n",eular(n));    return 0;   }

HDU 2824 The Euler function  筛法求欧拉函数

题目大意：求a到b范围的欧拉函数的和。

题解：筛法就欧拉函数。

#include <iostream>#include <cstdio>using namespace std;const int maxn=3000005;long long phi[maxn];int main(){    int i,j,a,b;    for(i=1;i<=maxn;i++) phi[i]=i;    for(i=2;i<=maxn;i+=2) phi[i]/=2;    for(i=3;i<=maxn;i+=2)if(phi[i]==i){      for(j=i;j<=maxn;j+=i)        phi[j]=phi[j]/i*(i-1);    }    while(scanf("%d%d",&a,&b)!=EOF){        long long ans=0;        for(i=a;i<=b;i++)ans+=phi[i];        cout<<ans<<endl;    }    return 0;}

HDU 1787 GCD Again  欧拉函数求补集

题目大意：求小于n的gcd(i,n)大于1的个数

题解：欧拉函数直接求gcd(i,n)==1的个数  用n减即可

#include <cstdio>int Eular(int n){    int ret=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;    return ret;}int main(){    int n;     while(scanf("%d",&n),n!=0)printf("%d\n",n-Eular(n)-1);    return 0;}

欧拉函数