sicily 1089 欧拉函数递推

//f[n] = f[n-1] + fai[n] //欧拉函数 质因子个数/n 包括本身 //fai[n] = n * (1 - 1/a)*.... a为质因子 #include <iostream> #include <cstring> #include <cmath> #define mx 1000010 using namespace std; int prime[mx]; bool isprime[mx]; long long f[1000010]; //long long 贡献一次wa double fai[1000010]; void primeList() { memset( isprime,true,sizeof( isprime ) ); for( int i = 2;i < mx;i++ ) { if( isprime[i] ) prime[++prime[0]] = i; for( int j = 1; j <= prime[0] && i * prime[j] < mx;j++ ) { isprime[i*prime[j]] = false; if( 0 == i % prime[j] ) break; } } } int main() { primeList(); f[2] = 1;f[3] = 3; for( int i = 4;i <= 1000000;i++ ) fai[i] = i; for( int i = 2;i <= 1000000;i++ ) //一开始把 i<sqrt() 当然WA。。 { if( isprime[i] ) { for( int j = i;j <= 1000000;j += i ) // fai = fai * (1-1/a) *(1-1/b)*... a b 为其质因子 { fai[j] = fai[j] / i * ( i - 1 ); } } } for( int i = 4;i <= 1000000;i++ ) { f[i] = f[i-1] + fai[i]; } int n; while( cin>>n && n != 0) cout<<f[n]<<endl; return 0; }