poj 2478: Farey Sequence

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstdlib>
 4 #include<cmath>
 5 #include<algorithm>
 6 #include<cstring>
 7 #include<queue>
 8 #include<vector>
 9 using namespace std;
10 typedef long long LL;
11 const LL maxn=1e6+5;
12 LL N,tot,ANS;
13 LL prime[maxn],phi[maxn];
14 bool not_p[maxn];
15 void shai(){
16     not_p[1]=1;
17     for(LL i=1;i<maxn;i++){
18         if(not_p[i]==false){
19             prime[++tot]=i;
20             phi[i]=i-1;
21         }
22         for(LL j=1;j<=tot;j++){
23             LL k=prime[j]*i;
24             if(k>maxn) break;
25             not_p[k]=true;
26             if(i%prime[j]!=0){
27                 phi[k]=phi[i]*phi[prime[j]];
28             }
29             else{
30                 phi[k]=phi[i]*prime[j];
31                 break;
32             }
33         }
34     }
35 }
36 int main(){
37     shai();
38     while(scanf("%lld",&N)&&N){
39         ANS=0;
40         for(LL i=2;i<=N;i++){
41             ANS+=phi[i];
42         }
43         printf("%lld\n",ANS);
44     }
45     return 0;
46 }