对正整数n，欧拉函数是少于或等于n的数中与n互质的数的数目。此函数以其首名研究者欧拉命名，它又称为Euler's totient function、φ函数、欧拉商数等。例如：φ(8) = 4（Phi(8) = 4），因为1,3,5,7均和8互质。

 

Input

输入一个数N。(2 <= N <= 10^9)

Output

输出Phi(n)。

Input示例

8

Output示例

4

代码

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 using namespace std; 6  7 int a; 8 int euler(int n){ //返回euler(n)    9      int res=n,a=n;  10      for(int i=2;i*i<=a;i++){  11          if(a%i==0){  12              res=res/i*(i-1);//先进行除法是为了防止中间数据的溢出   13              while(a%i==0) a/=i;  14          }  15      }  16      if(a>1) res=res/a*(a-1);  17      return res;  18 }  19 20 int main(){21 //    freopen("01.in","r",stdin);22     while(scanf("%d",&a)==1&&a){23         cout<
          
           <
          
         
        
       
      

这是根据定义直接求出的函数，

到处看了一些博客，百度百科讲得最详细，

 

转载一下两种模板：

对正整数n，欧拉函数是少于或等于n的数中与n互质的数的数目。

例如euler(8)=4，因为1,3,5,7均和8互质。Euler函数表达通式：euler(x)=x(1-1/p1)(1-1/p2)(1-1/p3)(1-1/p4)…(1-1/pn),其中p1,p2……pn为x的所有素因数，x是不为0的整数。euler(1)=1（唯一和1互质的数就是1本身）。 

欧拉公式的延伸：

一个数的所有质因子之和是euler(n)*n/2。

那么如何变成实现欧拉函数呢？下面通过两种不同的方法来实现。

第一种方法是直接根据定义来实现，同时第一种方法也是第二种筛法的基础，当好好理解。

 

 

1 //直接求解欧拉函数   2 int euler(int n){ //返回euler(n)    3      int res=n,a=n;   4      for(int i=2;i*i<=a;i++){   5          if(a%i==0){   6              res=res/i*(i-1);//先进行除法是为了防止中间数据的溢出    7              while(a%i==0) a/=i;   8          }   9      }  10      if(a>1) res=res/a*(a-1);  11      return res;  12 }  13   14 //筛选法打欧拉函数表   15 #define Max 1000001  16 int euler[Max];  17 void Init(){   18      euler[1]=1;  19      for(int i=2;i