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