1 1 #include<iostream> 2 2 #include<cstdlib> 3 3 #include<cstdio> 4 4 #include<cstring> 5 5 #include<algorithm> 6 6 #include<cmath> 7 7 using namespace std; 8 8 int phi[66000]; 9 9 int main() 10 10 { 11 11 int i , j ; 12 12 for ( i = 2 ; i <= 65536 ; i ++ ) 13 13 phi[i]=0; 14 14 phi[1]=1; 15 15 for ( i = 2 ; i <= 65536 ; i ++ ) 16 16 if ( !phi[i] ) 17 17 { 18 18 for ( j = i ; j <= 65536 ; j += i ) 19 19 { 20 20 if ( !phi[j] ) 21 21 phi[j] = j ; 22 22 phi[j] = phi[j] / i * (i - 1 ) ; 23 23 } 24 24 } 25 25 26 26 int n ; 27 27 while ( cin >> n ) 28 28 cout<<phi[n-1]<<endl; 29 29 30 30 return 0; 31 31 }