poj2478-Farey Sequence

素数筛法+欧拉函数

[cpp]
#include<iostream>
#include<cstdio>
#include<cstring>

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 ;
}

#include<iostream>
#include<cstdio>
#include<cstring>

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 ;
}

补充：软件开发 , C++ ,