estrela.cpp

//
//  estrela.cpp
//  programas2
//
//  Created by Lucca Siaudzionis on 18/03/13.
//  Copyright (c) 2013 Luccasiau. All rights reserved.
//
 
#include <cstdio>
#include <vector>
#define MAXP 55050
using namespace std;
 
int n;
int marc[MAXP];
vector<int> primos;
 
 
int isprime(int x){
     
    if(x == 2) return 0;
     
    for(int i = 0;i<primos.size();i++){
         
        if(primos[i]*primos[i] > x) break;
         
        if(x % primos[i] == 0) return primos[i];
         
    }
     
    return 0;
     
}
 
int maxexp(int d,int x){
     
    if(x % d) return 0;
    return 1+(maxexp(d,x/d));
     
}
 
int phi_prime(int p,int exp){
     
    int aux = 1;
    for(int i = 1;i<=exp-1;i++) aux *= p;
     
    return aux*(p-1);
     
}
 
 
int phi(int x){
     
    if(x <= 1) return 1;
     
    int davez = isprime(x);
     
    if(!davez) return x-1;
 
    int exp = maxexp(davez,x);
    int aux=1;
    for(int i = 1;i<=exp;i++) aux *= davez;
     
    return phi_prime(davez,exp)*phi(x/aux);
     
}
 
 
 
int main(){
     
    for(int i = 2;i<MAXP;i++){ // Crivo de Erastótenes
        if(!marc[i]){
            primos.push_back(i);
            for(int j = i+i;j<MAXP;j+=i) marc[j] = 1;
        }
    }
     
     
    while( scanf("%d",&n) != EOF ){
        printf("%d\n",phi(n)/2);
    }
    
    return 0;
}