http://acm.hdu.edu.cn/showproblem.php?pid=1286

欧拉函数：在数论，对正整数n，欧拉函数是少于或等于n的数中与n互质的数的数目。此函数以其首名研究者欧拉命名，它又称为Euler's totient function、φ函数、欧拉商数等。 例如φ(8)=4，因为1,3,5,7均和8互质。

//HDOJ 1286 Code By NetBeans 6.9.1
#include <iostream>

using namespace std;

int euler( int x );

int main( )
{
    int CN;
    cin >> CN;
    while( CN-- )
    {
        int N;
        cin >> N;
        cout << euler( N ) << endl;
    }
    return 0;
}

int euler( int x )
{
    int result = x;
    for( int i = 2; i * i <= x; ++i )
    {
        if( x % i == 0 )
        {
            result = result * ( i - 1 ) / i;
            while( x % i == 0 )
            {
                x /= i;
            }
        }
    }
    if( x > 1 )
    {
        result = result * ( x - 1 ) / x;
    }
    return result;
}
#if gongzi
#endif

欧拉函数还可以写成这样：

int euler( int x )
{
    int result = 1;
    for( int i = 2; i * i <= x; ++i )
    {
        if( x % i == 0 )
        {
            x /= i;
            result *= i - 1;
            while( x % i == 0 )
            {
                x /= i;
                result *= i;
            }
        }
    }
    if( x > 1 )
    {
        result *= x - 1;
    }
    return result;
}