页面设计参考_建筑公司网站源码_百度推广关键词规划师_b站大全永不收费2023入口在哪

样例输入

2
1 2
1 1000000

样例输出

1
3626619

解题思路：这题和前面Factorization 类似https://blog.csdn.net/m0_75005390/article/details/143178333?spm=1001.2014.3001.5501，欧筛+前缀和

找规律 f[i*j]=f[i]+f[j]

f[2]=1

f[4]=f[2]+f[2]=2

f[8]=f[4*2]=f[4]+f[2]=3

#include<stdio.h>
#define N 1000005
int a[N]={};
int b[N]={};
int f[N]={};
void init(){int i,j,k=0;a[0]=1,a[1]=1;for(i=2;i<N;i++){if(a[i]==0){b[k++]=i;f[i]=1;}for(j=0;j<k;j++){if(i*b[j]>N)break;a[i*b[j]]=1;f[i*b[j]]=f[i]+f[b[j]];if(i%b[j]==0)break; }} for(i=0;i<N;i++){f[i]+=f[i-1];}
}
void Sol(){int a,b;scanf("%d%d",&a,&b);printf("%d\n",f[b]-f[a-1]);
}
int main(){int T;scanf("%d",&T);init();while(T--){Sol();}
}