> #include <stdio.h> 
> #include <string.h> 
> #include <math.h> 
> #define max 1000000 
> #define maxn 10000 
> 
> bool c[maxn+1]; 
> int a[10],e[max+1],b[maxn+1],f[max+1]; 
> __int64 d[max+1]; 
> 
> void init() 
> { 
>         int i,j,n,t; 
> 
>         memset(c,0,sizeof(c)); 
>         memset(b,0,sizeof(b)); 
> 
>         for (i=4;i<=maxn;i+=2) 
>                 c[i]=1; 
>         n=maxn/3+1; 
>         j=0; 
>         for (i=2;i<=maxn;i++) 
>                 if (c[i]==0) 
>                 { 
>                         b[++j]=i; 
>                         for (t=i;t<=maxn;t+=i) 
>                                 c[t]=1; 
>                 } 
> } 
> 
> int main() 
> { 
>         init(); 
>         int i,j,n,s,r,k,t; 
> 
>         
>         memset(d,0,sizeof(d)); 
>         memset(e,0,sizeof(e)); 
>         memset(f,0,sizeof(f)); 
>         for (i=1;i<=max;i++) 
>         { 
>               if (f[i]==0) 
>               { 
>                         memset(a,0,sizeof(a)); 
>                         r=0; 
>                         n=i; 
>                         s=sqrt((double)n)+1; 
>                         for (j=1;b[j]<=s;j++) 
>                         { 
>                                 if (n%b[j]==0) 
>                                 { 
>                                         r++; 
>                                         a[r]=b[j]; 
>                                         while (n%b[j]==0) 
>                                                 n/=b[j]; 
>                                 } 
>                         } 
>                         if (n!=1) 
>                         { 
>                                 r++; 
>                                 a[r]=n; 
>                         } 
>                         e[i]=i; 
>                         for (t=1;t<=r;t++) 
>                                 e[i]=e[i]/a[t]*(a[t]-1); 
>                         for (t=1;t<=r;t++)
>                                 for (k=i*a[t];k<=max && k>0;k*=a[t]) 
>                                 { 
> 								//	printf("%d\n",k);
>                                         f[k]=r;e[k]=e[k/a[t]]*a[t]; 
>                                 } 
>                 }
>         } 
>         d[1]=e[1]=0; 
>         d[2]=e[2]; 
>         for (i=2;i<=max;i++) 
>                 d[i]=d[i-1]+e[i]; 
>         while (scanf("%d",&n) && n) 
>         { 
>                 printf("%I64d\n",d[n]); 
>         } 
>         return 0; 
> } 

• Re:暴力优化，然后用最原始的办法求euler phi也能过 (179) wqb0039 2006-09-29 09:35:25