基准时间限制：1 秒 空间限制：131072 KB 分值: 0 

 收藏

 关注

对正整数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 思路：模板题。

#include
       
        int n,ans;int Get_phi(int n){    int i,m=n;    ans = n;    for(i = 2; i*i <= m; i ++)        if(n%i == 0)//找到第一个素因子         {            ans = ans/i*(i-1);//欧拉函数性质的应用             while(n%i == 0)//约去所有素因子                 n/=i;        }    if( n > 1)        ans = ans/n*(n-1);    return ans;}int main(){    while(scanf("%d",&n)!=EOF)    {        ans = Get_phi(n);        printf("%d\n",ans);    }    return 0;}