题目描述
如果一个合数x=p⋅q,p,q是素数且p≠q，我们称x是双素数。 现给你一个区间[a,b]，求区间内的的双素数个数。
输入
第一行是一个整数T(1≤T≤30000)，为样例的数目。 以后每行一个样例，为两个整数a,b(1≤a≤b≤106)
输出
依次每行输出一个样例的结果。
样例输入
3 1 10 1 100 1 1000000
样例输出
2 30 209867
AC代码
#include<stdio.h>
#define N 1000005
int a[N]={};
int f[N]={};
void init(){
int i,j;
a[0]=1,a[1]=1;
//埃筛
for(i=2;i<N;i++){
if(a[i]==0){
for(j=2*i;j<N;j+=i){
a[j]=1;
}
}
}
//计算f[i]
for(i=2;i<1005;i++){
if(a[i]==0){
for(j=i+1;i*j<N;j++){
if(a[j]==0){
f[i*j]=1;
}
}
}
}
//前缀和
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();
}
} 解题思路：利用前缀和知识，满足条件为1，前缀和累计即可。
