totient

gistfile1.c

//http://mathworld.wolfram.com/TotientFunction.html
//use (13) and (14)
int totient(int n) {
    int ret = 1;
    for ( int i = 2; n != 1; i++ ) {
        if ( n % i == 0 ) {
            int pow = 1;
            while ( n % i == 0 ) {
                n = n / i;
                pow *= i;
            }
            ret = ret * pow / i * (i - 1);
        }
    }
    return ret;
}