Lightoj 1007 - Mathematically Hard

http://lightoj.com/volume_showproblem.php?problem=1007

1. #include <bits/stdc++.h>
2. using namespace std;
3. #define ll unsigned long long int
4. #define N 5000010
5. ll ph[N];
6. void phi(){
7.     ph[1] = 0;
8.     for(int i = 2; i <N; i++) if(!ph[i]){
9.         for(int j  = i; j <N; j+= i){
10.             if(!ph[j]) ph[j] = j;
11.             ph[j] = (ph[j]*(i-1))/i;
12.         }
13.     }
14.     for(int i=2;i<N;i++){
15.             ph[i]*=ph[i];
16.             ph[i]+=ph[i-1];
17.     }
18. }
20. int main(){
21.     phi();
22.     int ts;
23.     cin>>ts;
24.     for(int k = 1; k <= ts; k++){
25.         int a, b, c;
26.         scanf("%d%d", &a, &b);
27.         printf("Case %d: %llu\n", k, ph[b]-ph[a-1]);
28.         //cout<<"Case "<<k<<": <<ph[b]-ph[a-1]<<endl;
29.     }
30.     return 0;
31. }