欧拉函数

 1 #include <iostream>
 2 
 3 using namespace std;
 4 
 5 bool Euler(int a,int n)   //Euler就是欧拉的意思 
 6 {
 7     int i;
 8     if(n%2==0 && a%2==0) return 0; //因为下面的循环当 i==1 || i==2 时不执行 
 9     for(i=2;i<a;i++)
10     {
11         if(a%i==0 && n%i==0) return 0;   //判断是否互质 
12     }
13     //printf("%d\n",a);
14     return 1;
15 }
16 int main()
17 {
18     int n;
19     scanf("%d",&n);
20     int ans=0;
21     for(int i=1;i<n;i++)
22     {
23         if(Euler(i,n)) ans++;   //如果互质ans++ 
24     }
25     printf("%d",ans);
26     //system("pause");
27     return 0;
28 }