素数筛法+欧拉函数
#include#include #include using namespace std; #define maxn 1000005 #define INT __int64 int Prime[ maxn + 1 ] ;INT ans[ maxn + 1 ] ;void prime(){ memset( Prime , 0 , sizeof( Prime ) ) ; Prime[ 0 ] = Prime[ 1 ] = 1 ; for( int i = 2 ; i * i <= maxn ; ++i ) { if( !Prime[ i ] ) { for( int j = i * i ; j <= maxn ; j += i ) Prime[ j ] = 1 ; } }}void enlerfun(){ for( int i = 1 ; i <= maxn ; ++i ) ans[ i ] = i ; for( int i = 2 ; i <= maxn ; ++i ) { if( !Prime[ i ] ) for( int j = i ; j <= maxn ; j += i ) { ans[ j ] = ans[ j ] / i * ( i - 1 ) ; } }} int main(){ int n ; prime() ; enlerfun() ; for( int i = 3 ; i <= maxn ; ++i ) ans[ i ] += ans[ i - 1 ] ; while( ~scanf( "%d" , &n ) && n ) { printf( "%I64d\n" , ans[ n ] ) ; } return 0 ;}