> 
ft

线性筛素数,线性求欧拉函数值,再累加!


#include<iostream>
#include<string.h>
using namespace std;
#define Max 1000001
bool flag[Max];int prime[80000],a[Max];
int p_num,i,j,n;__int64 b[Max];
void getP() 
{    p_num = 0;
     memset(flag,false, sizeof(flag) );
     for ( i = 2; i < Max; i++ ) 
     {
         if ( !flag[i] ) prime[p_num++] = i;
         for ( j = 0; j < p_num && i * prime[j] <  Max; j++ ) 
         {
             flag[ i * prime[j] ] = true;
             if ( i % prime[j] == false ) 
              break;
         }
     }
     a[0]=a[1]=0;
	 for(i=2;i<Max;i++)
     {if(!flag[i]) a[i]=i-1;
      else 
	  {   for(j=0;j<p_num;++j)
            if(i%prime[j]==0) break;
          if((i/prime[j])%prime[j]==0) a[i]=a[i/prime[j]]*(prime[j]);
          else  a[i]=a[i/prime[j]]*(prime[j]-1);
	  }
	}
    memset(b,0,sizeof(b));
	for(i=2;i<Max;i++)
	b[i]=a[i]+b[i-1];
}
int main()
{   getP();
   while(scanf("%d",&n))
   {if(n==0) break;
    printf("%I64d\n",b[n]);
   }
   
   system("pause");
   return 0;
}