UVa : 10179


// @BEGIN_OF_SOURCE_CODE

#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <cctype>
#include <vector>
#include <map>
#include <set>
#include <math.h>
#define For(a) for ( i = 0; i < a; i++ )
#define Rep(a, b) for ( i = a; i <= b; i++ )
#define N 1000000
using namespace std;

int phi (int n)
{
    if ( n == 1 )
        return 1;

    int output = n;

    if ( n % 2 == 0 ) {
        output -= (output / 2);
        while ( n % 2 == 0 )
            n /= 2;
    }

    for ( int i = 3; i * i <= n; i += 2 ) {
        if ( n % i == 0 ) {
            output -= (output / i);
            while ( n % i == 0 )
                n /= i;
        }
    }

    if ( n > 1 )
        output -= (output / n);

    return output;
}

int main ()
{
    int n;

    while ( scanf ("%d", &n) && n ) {
        printf ("%d\n", phi (n));
    }

    return 0;
}

// @END_OF_SOURCE_CODE
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s