xtu oj 求和
输入格式
第一行是一个整数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]);
}
}