POJ.1284 Primitive Roots

1.Problem
http://poj.org/problem?id=1284

2.Idea
Primitive roots, Euler function

3.Source

 int euler[N];  
 void solve()  
 {  
      for (int i = 0; i < N; i++) euler[i] = i;  
      for (int i = 2; i < N; i++) {  
           if (euler[i] == i) {  
                for (int j = i; j < N; j += i) {  
                     euler[j] = euler[j] / i * (i - 1);  
                }  
           }  
      }  
      int p;  
      while (scanf("%d", &p)>0) {  
           printf("%d\n", euler[p - 1]);  
      }  
 }  
 int main() {  
      ios_base::sync_with_stdio(0); cin.tie(0); cout << fixed << setprecision(13);  
      solve();  
      return 0;  
 }