欧拉函数的应用
#include <stdio.h>
#include <math.h>

const int MAX = 32000;

int prime[MAX];

int number[MAX];

int find ( int n )
{

    
    number[0] = number[1] = 1;
    for ( int i=2; i<=n; i++ )
    {
        number[i] = 0;
    }
    
    for ( int j=2; j<=n; j++ )
    {
        for ( int z=j+j; z<=n; z+=j )
        {
            if ( ! number[z] )
            {
                number[z] = 1;
            }
        }
    }
    
    int p = 0;
    for ( i=0; i<=n; i++ )
    {
        if ( !number[i] )
        {
            prime[p++] = i;
        }
    }
    
    return p;
}

int num[MAX];
int pre;

int f ( int n, int len )
{
    
    int l, r, mid;
    int flag = 1;
    
    int n2 = ( int )( sqrt ( (double)n ) ) + 1;

    l = 0;
    r = len - 1;
    while ( l<=r )
    {
        mid = ( l + r ) / 2;
        if ( prime[mid] > n2 )
        {
            r = mid - 1;
        }
        else
        {
            l = mid + 1;
        }
    }
    
    for ( int i=r; i>=0; i-- )
    {
        if ( ! ( n % prime[i] ) )
        {
            flag = 0;
            while ( ! ( n % prime[i] ) )
            {
                num[pre++] = prime[i];
                n /= prime[i];
            }
            break;
        }
    }
    if ( flag )
    {
        num[pre++] = n;
        n = 1;
    }
    
    return n;
}

int power ( int a, int n )
{

    int sum = 1;
    int count = a;

    while ( n )
    {
        if ( n & 1 )
        {
            sum *= count;
        }
        n >>= 1;
        count *= count;
    }
    return sum;
}

int main ()
{

    int n;
    int sum, count;

    int len = find ( MAX );
    while ( scanf ( "%d", &n ) != EOF && n )
    {
        if ( n == 1 )
        {
            printf ( "0\n" );
            continue;
        }
        pre = 0;
        while ( n > 1 )
        {
            n = f ( n, len );
        }
        count  = 1;
        sum = 1;
        for ( int i=0; i<pre-1; i++ )
        {
            if ( num[i] != num[i+1] )
            {
                sum *= (num[i]-1)*power ( num[i], count-1 );
                count = 1;
            }
            else
            {
                count ++;
            }
        }
        sum *= (num[i]-1)*power ( num[i], count-1 );

        printf ( "%d\n", sum );
    }
    return 0;
}