Note the following three special properties

Programming using euler function and its different prime factors of the relationship, sieve method to calculate the euler function values of all numbers in a certain range.

1 #include<cstdio> 2 int euler(int n){2 int res=n,a=n; 5 for(int i=2; i*i<=a; I++) {/ / since the childhood trying to prime factors of n 6 if (a % I = = 0) {/ / if I were the prime factors of n 7 res = res/I * (I - 1); 8 while(a% I ==0) a/= I; If (a>1) res=res/a*(a-1); Return res; 13 } 14 int main(){ 15 int x; 16 scanf("%d",&x); 17 printf("%d",euler(x)); 18 return 0; 19}Copy the code
Table 2 #include<cstdio> 3 #define Max 1000001 4 int Euler [Max]; 5 void Init(){ 6 euler[1]=1; 7 for(int i=2; i<Max; i++) 8 euler[i]=i; 9 for(int i=2; i<Max; For (int j= I; int j= I; int j= I; j<Max; j+=i) 12 euler[j]=euler[j]/i*(i-1); // return (1/ I); return (1/ I); 14 } 15 int main() 16 { 17 Init(); 18 for(int i=1; i<=100; i++) 19 printf("%d\n",euler[i]); 20 return 0; 21}Copy the code