歐拉函數(shù)的應(yīng)用
#include <stdio.h>
#include <math.h>

const int MAX = 1000001;

int prime[MAX/5];
int len = 0;

__int64 dp[MAX];

int check ( int n )/*得到最小質(zhì)因數(shù)*/
{
    if ( !( n & 1 ) )
    {
        return 2;
    }

    int m = (int)sqrt ( (double)n );

    int l, r, mid;
    l = 0;
    r = len-1;
    while ( l <= r )
    {
        mid = ( l+r ) / 2;
        if ( prime[mid] > m )
        {
            r = mid - 1;
        }
        else
        {
            l = mid + 1;
        }
    }
    for ( int i=0; i<=r; i++ )
    {
        if ( n % prime[i] == 0 )
        {
            return prime[i];
        }
    }
    prime[len++] = n;
    return n;
}

void cup ()
{

    dp[1] = 1;
    dp[2] = 1;
    dp[3] = 2;
    dp[4] = 2;
    dp[5] = 4;
    prime[0] = 2;
    prime[1] = 3;
    prime[2] = 5;
    len = 3;
    for ( int i=6; i<MAX; i++ )
    {
        int min = check ( i );

        if ( (i / min) % min )
        {
            dp[i] = dp[i/min]*(min-1);
        }
        else
        {
            dp[i] = dp[i/min]*min;
        }
    }

    for ( i=3; i<MAX; i++ )
    {
        dp[i] += dp[i-1];
    }
}

int main ()
{

    int n;

    cup ();

    while ( scanf ( "%d", &n ) != EOF && n )
    {
        printf ( "%I64d\n", dp[n] );
    }
    return 0;
}