LightOJ - 1007 - Mathematically Hard

1. /****************#####    بِسْمِ اللَّهِ الرَّحْمَنِ الرَّحِيم   #####******************
2. __________________________________________________________________________
3. ######################  Ya-Seen Arafat(ACWizard) #########################
4. ######################        UAP-CSE-33B        #########################
5. *************************************************************************/
6. #include <bits/stdc++.h>
7. #define S 5000003
8. using namespace std;
9.  
10. bool prime[S];
11. __int64 primeD[S];
12.  
13. void seive(){
14.     int last;
15.     for(int i = 2; i <= S; i++){
16.         if(prime[i]){
17.             primeD[i] = i-1;
18.             for(int j = i+i; j <= S; j+=i){
19.                 prime[j] = false;
20.                 if(!primeD[j])primeD[j] = (__int64)j - (j/i);
21.                 else primeD[j] -= (primeD[j]/i);
22.             }
23.         }
24.     }
25.     for(int i = 2; i <= S; i++)primeD[i] *= primeD[i];
26. }
27.  
28. void cumulative_sum(){
29.     for(int i = 3; i <= S; i++){
30.         primeD[i] = primeD[i-1]+primeD[i];
31.     }
32. }
33.  
34. int main(){
35.     memset(prime, true, sizeof(prime));
36.     seive();
37.     cumulative_sum();
38.     int t, a, b, cs = 0;
39.     scanf("%d", &t);
40.     while(t--){
41.         scanf("%d %d", &a, &b);
42.         printf("Case %d: %llu\n", ++cs, primeD[b]-primeD[a-1]);
43.     }
44.     return 0;
45. }