输入格式

第一行是一个整数T(1≤T≤10000)，表示样例的个数。

以后每行两个整数a,b (1≤a≤b≤106)

输出格式

每行输出一个样例的结果，为一个整数。

样例输入

3
1 10
1 1000000
1000 2000

样例输出

21
424899695954
1099654

利用前缀和解题

标记素数

for(i=3;i<N;i++){
        for(j=2;j*j<=i;j++){
            if(i%j==0) break;
        }
        if(j*j>i) f[i]=1;
    }

AC代码

#include<stdio.h>
#define N 1000005
#define ll long long
ll f[N]={};
void init(){int i,j;f[2]=1;for(i=3;i<N;i++){for(j=2;j*j<=i;j++){if(i%j==0) break;}//标记素数 if(j*j>i) f[i]=1;}for(i=1;i<N;i++){if(f[i]==1)f[i]=f[i-1]-i;else f[i]=f[i-1]+i;} 
} 
int main(){int T;scanf("%d",&T);init();while(T--){int a,b;scanf("%d%d",&a,&b);printf("%lld\n",f[b]-f[a-1]);}
}